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), m_butterfly);
 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), m_butterfly);
 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), m_butterfly);
 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), m_butterfly);
 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), m_butterfly);
 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), m_butterfly);
 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), m_butterfly);
 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, m_butterfly);
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, m_butterfly);
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), m_butterfly);
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()), m_butterfly);
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()), m_butterfly);
1582 }
1583
1584 void JSObject::preventExtensions(VM& vm)
1585 {
1586     enterDictionaryIndexingMode(vm);
1587     if (isExtensible())
1588         setStructure(vm, Structure::preventExtensionsTransition(vm, structure()), m_butterfly);
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()), m_butterfly);
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), m_butterfly);
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         || indexIsSufficientlyBeyondLengthForSparseMap(i, m_butterfly->vectorLength())) {
1877         ASSERT(i <= MAX_ARRAY_INDEX);
1878         ensureArrayStorageSlow(vm);
1879         SparseArrayValueMap* map = allocateSparseIndexMap(vm);
1880         map->putEntry(exec, this, i, value, false);
1881         ASSERT(i >= arrayStorage()->length());
1882         arrayStorage()->setLength(i + 1);
1883         return;
1884     }
1885
1886     ensureLength(vm, i + 1);
1887
1888     RELEASE_ASSERT(i < m_butterfly->vectorLength());
1889     switch (indexingShape) {
1890     case Int32Shape:
1891         ASSERT(value.isInt32());
1892         m_butterfly->contiguousInt32()[i].setWithoutWriteBarrier(value);
1893         break;
1894
1895     case DoubleShape: {
1896         ASSERT(value.isNumber());
1897         double valueAsDouble = value.asNumber();
1898         ASSERT(valueAsDouble == valueAsDouble);
1899         m_butterfly->contiguousDouble()[i] = valueAsDouble;
1900         break;
1901     }
1902
1903     case ContiguousShape:
1904         m_butterfly->contiguous()[i].set(vm, this, value);
1905         break;
1906
1907     default:
1908         CRASH();
1909     }
1910 }
1911
1912 void JSObject::putByIndexBeyondVectorLengthWithArrayStorage(ExecState* exec, unsigned i, JSValue value, bool shouldThrow, ArrayStorage* storage)
1913 {
1914     VM& vm = exec->vm();
1915
1916     // i should be a valid array index that is outside of the current vector.
1917     ASSERT(i <= MAX_ARRAY_INDEX);
1918     ASSERT(i >= storage->vectorLength());
1919
1920     SparseArrayValueMap* map = storage->m_sparseMap.get();
1921
1922     // First, handle cases where we don't currently have a sparse map.
1923     if (LIKELY(!map)) {
1924         // If the array is not extensible, we should have entered dictionary mode, and created the sparse map.
1925         ASSERT(isExtensible());
1926
1927         // Update m_length if necessary.
1928         if (i >= storage->length())
1929             storage->setLength(i + 1);
1930
1931         // Check that it is sensible to still be using a vector, and then try to grow the vector.
1932         if (LIKELY(!indexIsSufficientlyBeyondLengthForSparseMap(i, storage->vectorLength())
1933             && isDenseEnoughForVector(i, storage->m_numValuesInVector)
1934             && increaseVectorLength(vm, i + 1))) {
1935             // success! - reread m_storage since it has likely been reallocated, and store to the vector.
1936             storage = arrayStorage();
1937             storage->m_vector[i].set(vm, this, value);
1938             ++storage->m_numValuesInVector;
1939             return;
1940         }
1941         // We don't want to, or can't use a vector to hold this property - allocate a sparse map & add the value.
1942         map = allocateSparseIndexMap(exec->vm());
1943         map->putEntry(exec, this, i, value, shouldThrow);
1944         return;
1945     }
1946
1947     // Update m_length if necessary.
1948     unsigned length = storage->length();
1949     if (i >= length) {
1950         // Prohibit growing the array if length is not writable.
1951         if (map->lengthIsReadOnly() || !isExtensible()) {
1952             if (shouldThrow)
1953                 throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
1954             return;
1955         }
1956         length = i + 1;
1957         storage->setLength(length);
1958     }
1959
1960     // We are currently using a map - check whether we still want to be doing so.
1961     // We will continue  to use a sparse map if SparseMode is set, a vector would be too sparse, or if allocation fails.
1962     unsigned numValuesInArray = storage->m_numValuesInVector + map->size();
1963     if (map->sparseMode() || !isDenseEnoughForVector(length, numValuesInArray) || !increaseVectorLength(exec->vm(), length)) {
1964         map->putEntry(exec, this, i, value, shouldThrow);
1965         return;
1966     }
1967
1968     // Reread m_storage after increaseVectorLength, update m_numValuesInVector.
1969     storage = arrayStorage();
1970     storage->m_numValuesInVector = numValuesInArray;
1971
1972     // Copy all values from the map into the vector, and delete the map.
1973     WriteBarrier<Unknown>* vector = storage->m_vector;
1974     SparseArrayValueMap::const_iterator end = map->end();
1975     for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
1976         vector[it->key].set(vm, this, it->value.getNonSparseMode());
1977     deallocateSparseIndexMap();
1978
1979     // Store the new property into the vector.
1980     WriteBarrier<Unknown>& valueSlot = vector[i];
1981     if (!valueSlot)
1982         ++storage->m_numValuesInVector;
1983     valueSlot.set(vm, this, value);
1984 }
1985
1986 void JSObject::putByIndexBeyondVectorLength(ExecState* exec, unsigned i, JSValue value, bool shouldThrow)
1987 {
1988     VM& vm = exec->vm();
1989
1990     // i should be a valid array index that is outside of the current vector.
1991     ASSERT(i <= MAX_ARRAY_INDEX);
1992
1993     switch (structure()->indexingType()) {
1994     case ALL_BLANK_INDEXING_TYPES: {
1995         if (indexingShouldBeSparse()) {
1996             putByIndexBeyondVectorLengthWithArrayStorage(
1997                 exec, i, value, shouldThrow,
1998                 ensureArrayStorageExistsAndEnterDictionaryIndexingMode(vm));
1999             break;
2000         }
2001         if (indexIsSufficientlyBeyondLengthForSparseMap(i, 0) || i >= MIN_SPARSE_ARRAY_INDEX) {
2002             putByIndexBeyondVectorLengthWithArrayStorage(
2003                 exec, i, value, shouldThrow, createArrayStorage(vm, 0, 0));
2004             break;
2005         }
2006         if (structure()->needsSlowPutIndexing()) {
2007             ArrayStorage* storage = createArrayStorage(vm, i + 1, getNewVectorLength(0, 0, i + 1));
2008             storage->m_vector[i].set(vm, this, value);
2009             storage->m_numValuesInVector++;
2010             break;
2011         }
2012
2013         createInitialContiguous(vm, i + 1)[i].set(vm, this, value);
2014         break;
2015     }
2016
2017     case ALL_UNDECIDED_INDEXING_TYPES: {
2018         CRASH();
2019         break;
2020     }
2021
2022     case ALL_INT32_INDEXING_TYPES: {
2023         putByIndexBeyondVectorLengthWithoutAttributes<Int32Shape>(exec, i, value);
2024         break;
2025     }
2026
2027     case ALL_DOUBLE_INDEXING_TYPES: {
2028         putByIndexBeyondVectorLengthWithoutAttributes<DoubleShape>(exec, i, value);
2029         break;
2030     }
2031
2032     case ALL_CONTIGUOUS_INDEXING_TYPES: {
2033         putByIndexBeyondVectorLengthWithoutAttributes<ContiguousShape>(exec, i, value);
2034         break;
2035     }
2036
2037     case NonArrayWithSlowPutArrayStorage:
2038     case ArrayWithSlowPutArrayStorage: {
2039         // No own property present in the vector, but there might be in the sparse map!
2040         SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get();
2041         if (!(map && map->contains(i)) && attemptToInterceptPutByIndexOnHole(exec, i, value, shouldThrow))
2042             return;
2043         // Otherwise, fall though.
2044     }
2045
2046     case NonArrayWithArrayStorage:
2047     case ArrayWithArrayStorage:
2048         putByIndexBeyondVectorLengthWithArrayStorage(exec, i, value, shouldThrow, arrayStorage());
2049         break;
2050
2051     default:
2052         RELEASE_ASSERT_NOT_REACHED();
2053     }
2054 }
2055
2056 bool JSObject::putDirectIndexBeyondVectorLengthWithArrayStorage(ExecState* exec, unsigned i, JSValue value, unsigned attributes, PutDirectIndexMode mode, ArrayStorage* storage)
2057 {
2058     VM& vm = exec->vm();
2059
2060     // i should be a valid array index that is outside of the current vector.
2061     ASSERT(hasArrayStorage(structure()->indexingType()));
2062     ASSERT(arrayStorage() == storage);
2063     ASSERT(i >= storage->vectorLength() || attributes);
2064     ASSERT(i <= MAX_ARRAY_INDEX);
2065
2066     SparseArrayValueMap* map = storage->m_sparseMap.get();
2067
2068     // First, handle cases where we don't currently have a sparse map.
2069     if (LIKELY(!map)) {
2070         // If the array is not extensible, we should have entered dictionary mode, and created the spare map.
2071         ASSERT(isExtensible());
2072
2073         // Update m_length if necessary.
2074         if (i >= storage->length())
2075             storage->setLength(i + 1);
2076
2077         // Check that it is sensible to still be using a vector, and then try to grow the vector.
2078         if (LIKELY(
2079                 !attributes
2080                 && (isDenseEnoughForVector(i, storage->m_numValuesInVector))
2081                 && !indexIsSufficientlyBeyondLengthForSparseMap(i, storage->vectorLength()))
2082                 && increaseVectorLength(vm, i + 1)) {
2083             // success! - reread m_storage since it has likely been reallocated, and store to the vector.
2084             storage = arrayStorage();
2085             storage->m_vector[i].set(vm, this, value);
2086             ++storage->m_numValuesInVector;
2087             return true;
2088         }
2089         // We don't want to, or can't use a vector to hold this property - allocate a sparse map & add the value.
2090         map = allocateSparseIndexMap(exec->vm());
2091         return map->putDirect(exec, this, i, value, attributes, mode);
2092     }
2093
2094     // Update m_length if necessary.
2095     unsigned length = storage->length();
2096     if (i >= length) {
2097         if (mode != PutDirectIndexLikePutDirect) {
2098             // Prohibit growing the array if length is not writable.
2099             if (map->lengthIsReadOnly())
2100                 return reject(exec, mode == PutDirectIndexShouldThrow, StrictModeReadonlyPropertyWriteError);
2101             if (!isExtensible())
2102                 return reject(exec, mode == PutDirectIndexShouldThrow, "Attempting to define property on object that is not extensible.");
2103         }
2104         length = i + 1;
2105         storage->setLength(length);
2106     }
2107
2108     // We are currently using a map - check whether we still want to be doing so.
2109     // We will continue  to use a sparse map if SparseMode is set, a vector would be too sparse, or if allocation fails.
2110     unsigned numValuesInArray = storage->m_numValuesInVector + map->size();
2111     if (map->sparseMode() || attributes || !isDenseEnoughForVector(length, numValuesInArray) || !increaseVectorLength(exec->vm(), length))
2112         return map->putDirect(exec, this, i, value, attributes, mode);
2113
2114     // Reread m_storage after increaseVectorLength, update m_numValuesInVector.
2115     storage = arrayStorage();
2116     storage->m_numValuesInVector = numValuesInArray;
2117
2118     // Copy all values from the map into the vector, and delete the map.
2119     WriteBarrier<Unknown>* vector = storage->m_vector;
2120     SparseArrayValueMap::const_iterator end = map->end();
2121     for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
2122         vector[it->key].set(vm, this, it->value.getNonSparseMode());
2123     deallocateSparseIndexMap();
2124
2125     // Store the new property into the vector.
2126     WriteBarrier<Unknown>& valueSlot = vector[i];
2127     if (!valueSlot)
2128         ++storage->m_numValuesInVector;
2129     valueSlot.set(vm, this, value);
2130     return true;
2131 }
2132
2133 bool JSObject::putDirectIndexBeyondVectorLength(ExecState* exec, unsigned i, JSValue value, unsigned attributes, PutDirectIndexMode mode)
2134 {
2135     VM& vm = exec->vm();
2136
2137     // i should be a valid array index that is outside of the current vector.
2138     ASSERT(i <= MAX_ARRAY_INDEX);
2139
2140     if (attributes & (ReadOnly | Accessor))
2141         notifyPresenceOfIndexedAccessors(vm);
2142
2143     switch (structure()->indexingType()) {
2144     case ALL_BLANK_INDEXING_TYPES: {
2145         if (indexingShouldBeSparse() || attributes) {
2146             return putDirectIndexBeyondVectorLengthWithArrayStorage(
2147                 exec, i, value, attributes, mode,
2148                 ensureArrayStorageExistsAndEnterDictionaryIndexingMode(vm));
2149         }
2150         if (i >= MIN_SPARSE_ARRAY_INDEX) {
2151             return putDirectIndexBeyondVectorLengthWithArrayStorage(
2152                 exec, i, value, attributes, mode, createArrayStorage(vm, 0, 0));
2153         }
2154         if (structure()->needsSlowPutIndexing()) {
2155             ArrayStorage* storage = createArrayStorage(vm, i + 1, getNewVectorLength(0, 0, i + 1));
2156             storage->m_vector[i].set(vm, this, value);
2157             storage->m_numValuesInVector++;
2158             return true;
2159         }
2160
2161         createInitialContiguous(vm, i + 1)[i].set(vm, this, value);
2162         return true;
2163     }
2164
2165     case ALL_UNDECIDED_INDEXING_TYPES: {
2166         convertUndecidedForValue(exec->vm(), value);
2167         // Reloop.
2168         return putDirectIndex(exec, i, value, attributes, mode);
2169     }
2170
2171     case ALL_INT32_INDEXING_TYPES: {
2172         if (attributes & (ReadOnly | Accessor)) {
2173             return putDirectIndexBeyondVectorLengthWithArrayStorage(
2174                 exec, i, value, attributes, mode, convertInt32ToArrayStorage(vm));
2175         }
2176         if (!value.isInt32()) {
2177             convertInt32ForValue(vm, value);
2178             return putDirectIndexBeyondVectorLength(exec, i, value, attributes, mode);
2179         }
2180         putByIndexBeyondVectorLengthWithoutAttributes<Int32Shape>(exec, i, value);
2181         return true;
2182     }
2183
2184     case ALL_DOUBLE_INDEXING_TYPES: {
2185         if (attributes & (ReadOnly | Accessor)) {
2186             return putDirectIndexBeyondVectorLengthWithArrayStorage(
2187                 exec, i, value, attributes, mode, convertDoubleToArrayStorage(vm));
2188         }
2189         if (!value.isNumber()) {
2190             convertDoubleToContiguous(vm);
2191             return putDirectIndexBeyondVectorLength(exec, i, value, attributes, mode);
2192         }
2193         double valueAsDouble = value.asNumber();
2194         if (valueAsDouble != valueAsDouble) {
2195             convertDoubleToContiguous(vm);
2196             return putDirectIndexBeyondVectorLength(exec, i, value, attributes, mode);
2197         }
2198         putByIndexBeyondVectorLengthWithoutAttributes<DoubleShape>(exec, i, value);
2199         return true;
2200     }
2201
2202     case ALL_CONTIGUOUS_INDEXING_TYPES: {
2203         if (attributes & (ReadOnly | Accessor)) {
2204             return putDirectIndexBeyondVectorLengthWithArrayStorage(
2205                 exec, i, value, attributes, mode, convertContiguousToArrayStorage(vm));
2206         }
2207         putByIndexBeyondVectorLengthWithoutAttributes<ContiguousShape>(exec, i, value);
2208         return true;
2209     }
2210
2211     case ALL_ARRAY_STORAGE_INDEXING_TYPES:
2212         return putDirectIndexBeyondVectorLengthWithArrayStorage(exec, i, value, attributes, mode, arrayStorage());
2213
2214     default:
2215         RELEASE_ASSERT_NOT_REACHED();
2216         return false;
2217     }
2218 }
2219
2220 void JSObject::putDirectNativeFunction(ExecState* exec, JSGlobalObject* globalObject, const PropertyName& propertyName, unsigned functionLength, NativeFunction nativeFunction, Intrinsic intrinsic, unsigned attributes)
2221 {
2222     StringImpl* name = propertyName.publicName();
2223     ASSERT(name);
2224
2225     JSFunction* function =
2226         JSFunction::create(exec, globalObject, functionLength, name, nativeFunction, intrinsic);
2227     putDirect(exec->vm(), propertyName, function, attributes);
2228 }
2229
2230 ALWAYS_INLINE unsigned JSObject::getNewVectorLength(unsigned currentVectorLength, unsigned currentLength, unsigned desiredLength)
2231 {
2232     ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);
2233
2234     unsigned increasedLength;
2235     unsigned maxInitLength = std::min(currentLength, 100000U);
2236
2237     if (desiredLength < maxInitLength)
2238         increasedLength = maxInitLength;
2239     else if (!currentVectorLength)
2240         increasedLength = std::max(desiredLength, lastArraySize);
2241     else {
2242         increasedLength = timesThreePlusOneDividedByTwo(desiredLength);
2243     }
2244
2245     ASSERT(increasedLength >= desiredLength);
2246
2247     lastArraySize = std::min(increasedLength, FIRST_VECTOR_GROW);
2248
2249     return std::min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
2250 }
2251
2252 ALWAYS_INLINE unsigned JSObject::getNewVectorLength(unsigned desiredLength)
2253 {
2254     unsigned vectorLength;
2255     unsigned length;
2256
2257     if (hasIndexedProperties(structure()->indexingType())) {
2258         vectorLength = m_butterfly->vectorLength();
2259         length = m_butterfly->publicLength();
2260     } else {
2261         vectorLength = 0;
2262         length = 0;
2263     }
2264
2265     return getNewVectorLength(vectorLength, length, desiredLength);
2266 }
2267
2268 template<IndexingType indexingShape>
2269 unsigned JSObject::countElements(Butterfly* butterfly)
2270 {
2271     unsigned numValues = 0;
2272     for (unsigned i = butterfly->publicLength(); i--;) {
2273         switch (indexingShape) {
2274         case Int32Shape:
2275         case ContiguousShape:
2276             if (butterfly->contiguous()[i])
2277                 numValues++;
2278             break;
2279
2280         case DoubleShape: {
2281             double value = butterfly->contiguousDouble()[i];
2282             if (value == value)
2283                 numValues++;
2284             break;
2285         }
2286
2287         default:
2288             CRASH();
2289         }
2290     }
2291     return numValues;
2292 }
2293
2294 unsigned JSObject::countElements()
2295 {
2296     switch (structure()->indexingType()) {
2297     case ALL_BLANK_INDEXING_TYPES:
2298     case ALL_UNDECIDED_INDEXING_TYPES:
2299         return 0;
2300
2301     case ALL_INT32_INDEXING_TYPES:
2302         return countElements<Int32Shape>(m_butterfly);
2303
2304     case ALL_DOUBLE_INDEXING_TYPES:
2305         return countElements<DoubleShape>(m_butterfly);
2306
2307     case ALL_CONTIGUOUS_INDEXING_TYPES:
2308         return countElements<ContiguousShape>(m_butterfly);
2309
2310     default:
2311         CRASH();
2312         return 0;
2313     }
2314 }
2315
2316 bool JSObject::increaseVectorLength(VM& vm, unsigned newLength)
2317 {
2318     // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
2319     // to the vector. Callers have to account for that, because they can do it more efficiently.
2320     if (newLength > MAX_STORAGE_VECTOR_LENGTH)
2321         return false;
2322
2323     ArrayStorage* storage = arrayStorage();
2324
2325     if (newLength >= MIN_SPARSE_ARRAY_INDEX
2326         && !isDenseEnoughForVector(newLength, storage->m_numValuesInVector))
2327         return false;
2328
2329     unsigned indexBias = storage->m_indexBias;
2330     unsigned vectorLength = storage->vectorLength();
2331     ASSERT(newLength > vectorLength);
2332     unsigned newVectorLength = getNewVectorLength(newLength);
2333
2334     // Fast case - there is no precapacity. In these cases a realloc makes sense.
2335     if (LIKELY(!indexBias)) {
2336         Butterfly* newButterfly = storage->butterfly()->growArrayRight(vm, structure(), structure()->outOfLineCapacity(), true, ArrayStorage::sizeFor(vectorLength), ArrayStorage::sizeFor(newVectorLength));
2337         if (!newButterfly)
2338             return false;
2339         m_butterfly = newButterfly;
2340         newButterfly->arrayStorage()->setVectorLength(newVectorLength);
2341         return true;
2342     }
2343
2344     // Remove some, but not all of the precapacity. Atomic decay, & capped to not overflow array length.
2345     unsigned newIndexBias = std::min(indexBias >> 1, MAX_STORAGE_VECTOR_LENGTH - newVectorLength);
2346     Butterfly* newButterfly = storage->butterfly()->resizeArray(
2347         vm,
2348         structure()->outOfLineCapacity(), true, ArrayStorage::sizeFor(vectorLength),
2349         newIndexBias, true, ArrayStorage::sizeFor(newVectorLength));
2350     if (!newButterfly)
2351         return false;
2352
2353     m_butterfly = newButterfly;
2354     newButterfly->arrayStorage()->setVectorLength(newVectorLength);
2355     newButterfly->arrayStorage()->m_indexBias = newIndexBias;
2356     return true;
2357 }
2358
2359 void JSObject::ensureLengthSlow(VM& vm, unsigned length)
2360 {
2361     ASSERT(length < MAX_ARRAY_INDEX);
2362     ASSERT(hasContiguous(structure()->indexingType()) || hasInt32(structure()->indexingType()) || hasDouble(structure()->indexingType()) || hasUndecided(structure()->indexingType()));
2363     ASSERT(length > m_butterfly->vectorLength());
2364
2365     unsigned newVectorLength = std::min(
2366         length << 1,
2367         MAX_STORAGE_VECTOR_LENGTH);
2368     unsigned oldVectorLength = m_butterfly->vectorLength();
2369     m_butterfly = m_butterfly->growArrayRight(
2370         vm, structure(), structure()->outOfLineCapacity(), true,
2371         oldVectorLength * sizeof(EncodedJSValue),
2372         newVectorLength * sizeof(EncodedJSValue));
2373     if (hasDouble(structure()->indexingType())) {
2374         for (unsigned i = oldVectorLength; i < newVectorLength; ++i)
2375             m_butterfly->contiguousDouble().data()[i] = QNaN;
2376     }
2377     m_butterfly->setVectorLength(newVectorLength);
2378 }
2379
2380 Butterfly* JSObject::growOutOfLineStorage(VM& vm, size_t oldSize, size_t newSize)
2381 {
2382     ASSERT(newSize > oldSize);
2383
2384     // It's important that this function not rely on structure(), for the property
2385     // capacity, since we might have already mutated the structure in-place.
2386
2387     return m_butterfly->growPropertyStorage(vm, structure(), oldSize, newSize);
2388 }
2389
2390 bool JSObject::getOwnPropertyDescriptor(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor)
2391 {
2392     unsigned attributes = 0;
2393     JSCell* cell = 0;
2394     PropertyOffset offset = object->structure()->get(exec->vm(), propertyName, attributes, cell);
2395     if (isValidOffset(offset)) {
2396         descriptor.setDescriptor(object->getDirect(offset), attributes);
2397         return true;
2398     }
2399
2400     unsigned i = propertyName.asIndex();
2401     if (i == PropertyName::NotAnIndex)
2402         return false;
2403
2404     switch (object->structure()->indexingType()) {
2405     case ALL_BLANK_INDEXING_TYPES:
2406     case ALL_UNDECIDED_INDEXING_TYPES:
2407         return false;
2408
2409     case ALL_INT32_INDEXING_TYPES:
2410     case ALL_CONTIGUOUS_INDEXING_TYPES: {
2411         Butterfly* butterfly = object->m_butterfly;
2412         if (i >= butterfly->vectorLength())
2413             return false;
2414         JSValue value = butterfly->contiguous()[i].get();
2415         if (!value)
2416             return false;
2417         descriptor.setDescriptor(value, 0);
2418         return true;
2419     }
2420
2421     case ALL_DOUBLE_INDEXING_TYPES: {
2422         Butterfly* butterfly = object->m_butterfly;
2423         if (i >= butterfly->vectorLength())
2424             return false;
2425         double value = butterfly->contiguousDouble()[i];
2426         if (value != value)
2427             return false;
2428         descriptor.setDescriptor(JSValue(JSValue::EncodeAsDouble, value), 0);
2429         return true;
2430     }
2431
2432     case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
2433         ArrayStorage* storage = object->m_butterfly->arrayStorage();
2434         if (i >= storage->length())
2435             return false;
2436         if (i < storage->vectorLength()) {
2437             WriteBarrier<Unknown>& value = storage->m_vector[i];
2438             if (!value)
2439                 return false;
2440             descriptor.setDescriptor(value.get(), 0);
2441             return true;
2442         }
2443         if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
2444             SparseArrayValueMap::iterator it = map->find(i);
2445             if (it == map->notFound())
2446                 return false;
2447             it->value.get(descriptor);
2448             return true;
2449         }
2450         return false;
2451     }
2452
2453     default:
2454         RELEASE_ASSERT_NOT_REACHED();
2455         return false;
2456     }
2457 }
2458
2459 bool JSObject::getPropertyDescriptor(ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor)
2460 {
2461     JSObject* object = this;
2462     while (true) {
2463         if (object->methodTable()->getOwnPropertyDescriptor(object, exec, propertyName, descriptor))
2464             return true;
2465         JSValue prototype = object->prototype();
2466         if (!prototype.isObject())
2467             return false;
2468         object = asObject(prototype);
2469     }
2470 }
2471
2472 static bool putDescriptor(ExecState* exec, JSObject* target, PropertyName propertyName, PropertyDescriptor& descriptor, unsigned attributes, const PropertyDescriptor& oldDescriptor)
2473 {
2474     if (descriptor.isGenericDescriptor() || descriptor.isDataDescriptor()) {
2475         if (descriptor.isGenericDescriptor() && oldDescriptor.isAccessorDescriptor()) {
2476             GetterSetter* accessor = GetterSetter::create(exec);
2477             if (oldDescriptor.getterPresent())
2478                 accessor->setGetter(exec->vm(), oldDescriptor.getterObject());
2479             if (oldDescriptor.setterPresent())
2480                 accessor->setSetter(exec->vm(), oldDescriptor.setterObject());
2481             target->putDirectAccessor(exec, propertyName, accessor, attributes | Accessor);
2482             return true;
2483         }
2484         JSValue newValue = jsUndefined();
2485         if (descriptor.value())
2486             newValue = descriptor.value();
2487         else if (oldDescriptor.value())
2488             newValue = oldDescriptor.value();
2489         target->putDirect(exec->vm(), propertyName, newValue, attributes & ~Accessor);
2490         if (attributes & ReadOnly)
2491             target->structure()->setContainsReadOnlyProperties();
2492         return true;
2493     }
2494     attributes &= ~ReadOnly;
2495     GetterSetter* accessor = GetterSetter::create(exec);
2496
2497     if (descriptor.getterPresent())
2498         accessor->setGetter(exec->vm(), descriptor.getterObject());
2499     else if (oldDescriptor.getterPresent())
2500         accessor->setGetter(exec->vm(), oldDescriptor.getterObject());
2501     if (descriptor.setterPresent())
2502         accessor->setSetter(exec->vm(), descriptor.setterObject());
2503     else if (oldDescriptor.setterPresent())
2504         accessor->setSetter(exec->vm(), oldDescriptor.setterObject());
2505
2506     target->putDirectAccessor(exec, propertyName, accessor, attributes | Accessor);
2507     return true;
2508 }
2509
2510 void JSObject::putDirectMayBeIndex(ExecState* exec, PropertyName propertyName, JSValue value)
2511 {
2512     unsigned asIndex = propertyName.asIndex();
2513     if (asIndex == PropertyName::NotAnIndex)
2514         putDirect(exec->vm(), propertyName, value);
2515     else
2516         putDirectIndex(exec, asIndex, value);
2517 }
2518
2519 class DefineOwnPropertyScope {
2520 public:
2521     DefineOwnPropertyScope(ExecState* exec)
2522         : m_vm(exec->vm())
2523     {
2524         m_vm.setInDefineOwnProperty(true);
2525     }
2526
2527     ~DefineOwnPropertyScope()
2528     {
2529         m_vm.setInDefineOwnProperty(false);
2530     }
2531
2532 private:
2533     VM& m_vm;
2534 };
2535
2536 bool JSObject::defineOwnNonIndexProperty(ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor, bool throwException)
2537 {
2538     // Track on the globaldata that we're in define property.
2539     // Currently DefineOwnProperty uses delete to remove properties when they are being replaced
2540     // (particularly when changing attributes), however delete won't allow non-configurable (i.e.
2541     // DontDelete) properties to be deleted. For now, we can use this flag to make this work.
2542     DefineOwnPropertyScope scope(exec);
2543
2544     // If we have a new property we can just put it on normally
2545     PropertyDescriptor current;
2546     if (!methodTable()->getOwnPropertyDescriptor(this, exec, propertyName, current)) {
2547         // unless extensions are prevented!
2548         if (!isExtensible()) {
2549             if (throwException)
2550                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to define property on object that is not extensible.")));
2551             return false;
2552         }
2553         PropertyDescriptor oldDescriptor;
2554         oldDescriptor.setValue(jsUndefined());
2555         return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributes(), oldDescriptor);
2556     }
2557
2558     if (descriptor.isEmpty())
2559         return true;
2560
2561     if (current.equalTo(exec, descriptor))
2562         return true;
2563
2564     // Filter out invalid changes
2565     if (!current.configurable()) {
2566         if (descriptor.configurable()) {
2567             if (throwException)
2568                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to configurable attribute of unconfigurable property.")));
2569             return false;
2570         }
2571         if (descriptor.enumerablePresent() && descriptor.enumerable() != current.enumerable()) {
2572             if (throwException)
2573                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change enumerable attribute of unconfigurable property.")));
2574             return false;
2575         }
2576     }
2577
2578     // A generic descriptor is simply changing the attributes of an existing property
2579     if (descriptor.isGenericDescriptor()) {
2580         if (!current.attributesEqual(descriptor)) {
2581             methodTable()->deleteProperty(this, exec, propertyName);
2582             return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributesOverridingCurrent(current), current);
2583         }
2584         return true;
2585     }
2586
2587     // Changing between a normal property or an accessor property
2588     if (descriptor.isDataDescriptor() != current.isDataDescriptor()) {
2589         if (!current.configurable()) {
2590             if (throwException)
2591                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change access mechanism for an unconfigurable property.")));
2592             return false;
2593         }
2594         methodTable()->deleteProperty(this, exec, propertyName);
2595         return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributesOverridingCurrent(current), current);
2596     }
2597
2598     // Changing the value and attributes of an existing property
2599     if (descriptor.isDataDescriptor()) {
2600         if (!current.configurable()) {
2601             if (!current.writable() && descriptor.writable()) {
2602                 if (throwException)
2603                     throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change writable attribute of unconfigurable property.")));
2604                 return false;
2605             }
2606             if (!current.writable()) {
2607                 if (descriptor.value() && !sameValue(exec, current.value(), descriptor.value())) {
2608                     if (throwException)
2609                         throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change value of a readonly property.")));
2610                     return false;
2611                 }
2612             }
2613         }
2614         if (current.attributesEqual(descriptor) && !descriptor.value())
2615             return true;
2616         methodTable()->deleteProperty(this, exec, propertyName);
2617         return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributesOverridingCurrent(current), current);
2618     }
2619
2620     // Changing the accessor functions of an existing accessor property
2621     ASSERT(descriptor.isAccessorDescriptor());
2622     if (!current.configurable()) {
2623         if (descriptor.setterPresent() && !(current.setterPresent() && JSValue::strictEqual(exec, current.setter(), descriptor.setter()))) {
2624             if (throwException)
2625                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change the setter of an unconfigurable property.")));
2626             return false;
2627         }
2628         if (descriptor.getterPresent() && !(current.getterPresent() && JSValue::strictEqual(exec, current.getter(), descriptor.getter()))) {
2629             if (throwException)
2630                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change the getter of an unconfigurable property.")));
2631             return false;
2632         }
2633     }
2634     JSValue accessor = getDirect(exec->vm(), propertyName);
2635     if (!accessor)
2636         return false;
2637     GetterSetter* getterSetter = asGetterSetter(accessor);
2638     if (descriptor.setterPresent())
2639         getterSetter->setSetter(exec->vm(), descriptor.setterObject());
2640     if (descriptor.getterPresent())
2641         getterSetter->setGetter(exec->vm(), descriptor.getterObject());
2642     if (current.attributesEqual(descriptor))
2643         return true;
2644     methodTable()->deleteProperty(this, exec, propertyName);
2645     unsigned attrs = descriptor.attributesOverridingCurrent(current);
2646     putDirectAccessor(exec, propertyName, getterSetter, attrs | Accessor);
2647     return true;
2648 }
2649
2650 bool JSObject::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor, bool throwException)
2651 {
2652     // If it's an array index, then use the indexed property storage.
2653     unsigned index = propertyName.asIndex();
2654     if (index != PropertyName::NotAnIndex) {
2655         // 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.
2656         // d. Reject if succeeded is false.
2657         // e. If index >= oldLen
2658         // e.i. Set oldLenDesc.[[Value]] to index + 1.
2659         // 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.
2660         // f. Return true.
2661         return object->defineOwnIndexedProperty(exec, index, descriptor, throwException);
2662     }
2663
2664     return object->defineOwnNonIndexProperty(exec, propertyName, descriptor, throwException);
2665 }
2666
2667 bool JSObject::getOwnPropertySlotSlow(ExecState* exec, PropertyName propertyName, PropertySlot& slot)
2668 {
2669     unsigned i = propertyName.asIndex();
2670     if (i != PropertyName::NotAnIndex)
2671         return getOwnPropertySlotByIndex(this, exec, i, slot);
2672     return false;
2673 }
2674
2675 JSObject* throwTypeError(ExecState* exec, const String& message)
2676 {
2677     return throwError(exec, createTypeError(exec, message));
2678 }
2679
2680 } // namespace JSC