Changeset 128400 in webkit for trunk/Source/JavaScriptCore/runtime

Timestamp:

Sep 12, 2012, 9:18:52 PM (13 years ago)

Author:

[email protected]

Message:

JSC should have property butterflies
​https://bugs.webkit.org/show_bug.cgi?id=91933

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

This changes the JSC object model. Previously, all objects had fast lookup for
named properties. Integer indexed properties were only fast if you used a
JSArray. With this change, all objects have fast indexed properties. This is
accomplished without any space overhead by using a bidirectional object layout,
aka butterflies. Each JSObject has a m_butterfly pointer where previously it
had a m_outOfLineStorage pointer. To the left of the location pointed to by
m_butterfly, we place all named out-of-line properties. To the right, we place
all indexed properties along with indexing meta-data. Though, some indexing
meta-data is placed in the 8-byte word immediately left of the pointed-to
location; this is in anticipation of the indexing meta-data being small enough
in the common case that m_butterfly always points to the first indexed
property.

This is performance neutral, except on tests that use indexed properties on
plain objects, where the speed-up is in excess of an order of magnitude.

One notable aspect of what this change brings is that it allows indexing
storage to morph over time. Currently this is only used to allow all non-array
objects to start out without any indexed storage. But it could be used for
some kinds of array type inference in the future.

• API/JSCallbackObject.h:

(JSCallbackObject):

• API/JSCallbackObjectFunctions.h:

(JSC::::getOwnPropertySlotByIndex):
(JSC):
(JSC::::getOwnNonIndexPropertyNames):

• API/JSObjectRef.cpp:
• CMakeLists.txt:
• GNUmakefile.list.am:
• JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.def:
• JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj:
• JavaScriptCore.xcodeproj/project.pbxproj:
• Target.pri:
• bytecode/ArrayProfile.h:

(JSC):
(JSC::arrayModeFromStructure):

• bytecompiler/BytecodeGenerator.cpp:

(JSC::BytecodeGenerator::emitDirectPutById):

• dfg/DFGAbstractState.cpp:

(JSC::DFG::AbstractState::execute):

• dfg/DFGAdjacencyList.h:

(JSC::DFG::AdjacencyList::AdjacencyList):
(AdjacencyList):

• dfg/DFGArrayMode.cpp:

(JSC::DFG::fromObserved):
(JSC::DFG::modeAlreadyChecked):
(JSC::DFG::modeToString):

• dfg/DFGArrayMode.h:

(DFG):
(JSC::DFG::modeUsesButterfly):
(JSC::DFG::modeIsJSArray):
(JSC::DFG::isInBoundsAccess):
(JSC::DFG::modeSupportsLength):

• dfg/DFGByteCodeParser.cpp:

(JSC::DFG::ByteCodeParser::handleGetByOffset):
(JSC::DFG::ByteCodeParser::parseBlock):

• dfg/DFGCSEPhase.cpp:

(JSC::DFG::CSEPhase::getPropertyStorageLoadElimination):
(JSC::DFG::CSEPhase::performNodeCSE):

• dfg/DFGFixupPhase.cpp:

(JSC::DFG::FixupPhase::fixupNode):
(JSC::DFG::FixupPhase::addNode):
(FixupPhase):
(JSC::DFG::FixupPhase::checkArray):

• dfg/DFGGraph.h:

(JSC::DFG::Graph::byValIsPure):

• dfg/DFGNode.h:

(JSC::DFG::Node::Node):
(Node):

• dfg/DFGNodeType.h:

(DFG):

• dfg/DFGOperations.cpp:

(JSC::DFG::putByVal):

• dfg/DFGOperations.h:
• dfg/DFGPredictionPropagationPhase.cpp:

(JSC::DFG::PredictionPropagationPhase::propagate):

• dfg/DFGRepatch.cpp:

(JSC::DFG::generateProtoChainAccessStub):
(JSC::DFG::tryCacheGetByID):
(JSC::DFG::tryBuildGetByIDList):
(JSC::DFG::emitPutReplaceStub):
(JSC::DFG::emitPutTransitionStub):
(JSC::DFG::tryBuildPutByIdList):

• dfg/DFGSpeculativeJIT.cpp:

(JSC::DFG::SpeculativeJIT::checkArray):
(JSC::DFG::SpeculativeJIT::compileGetIndexedPropertyStorage):
(JSC::DFG::SpeculativeJIT::compileGetArrayLength):
(JSC::DFG::SpeculativeJIT::compileAllocatePropertyStorage):
(JSC::DFG::SpeculativeJIT::compileReallocatePropertyStorage):

• dfg/DFGSpeculativeJIT.h:

(JSC::DFG::SpeculativeJIT::callOperation):
(JSC::DFG::SpeculativeJIT::emitAllocateBasicJSObject):

• dfg/DFGSpeculativeJIT32_64.cpp:

(JSC::DFG::SpeculativeJIT::cachedGetById):
(JSC::DFG::SpeculativeJIT::cachedPutById):
(JSC::DFG::SpeculativeJIT::compile):

• dfg/DFGSpeculativeJIT64.cpp:

(JSC::DFG::SpeculativeJIT::cachedGetById):
(JSC::DFG::SpeculativeJIT::cachedPutById):
(JSC::DFG::SpeculativeJIT::compile):

• dfg/DFGStructureCheckHoistingPhase.cpp:

(JSC::DFG::StructureCheckHoistingPhase::run):

• heap/CopiedSpace.h:

(CopiedSpace):

• jit/JIT.h:
• jit/JITInlineMethods.h:

(JSC::JIT::emitAllocateBasicJSObject):
(JSC::JIT::emitAllocateBasicStorage):
(JSC::JIT::emitAllocateJSArray):

• jit/JITOpcodes.cpp:

(JSC::JIT::emit_op_new_array):
(JSC::JIT::emitSlow_op_new_array):

• jit/JITPropertyAccess.cpp:

(JSC::JIT::emit_op_get_by_val):
(JSC::JIT::compileGetDirectOffset):
(JSC::JIT::emit_op_put_by_val):
(JSC::JIT::compileGetByIdHotPath):
(JSC::JIT::emit_op_put_by_id):
(JSC::JIT::compilePutDirectOffset):
(JSC::JIT::privateCompilePatchGetArrayLength):

• jit/JITPropertyAccess32_64.cpp:

(JSC::JIT::emit_op_get_by_val):
(JSC::JIT::emit_op_put_by_val):
(JSC::JIT::compileGetByIdHotPath):
(JSC::JIT::emit_op_put_by_id):
(JSC::JIT::compilePutDirectOffset):
(JSC::JIT::compileGetDirectOffset):
(JSC::JIT::privateCompilePatchGetArrayLength):

• jit/JITStubs.cpp:

(JSC::DEFINE_STUB_FUNCTION):

• jsc.cpp:
• llint/LLIntSlowPaths.cpp:

(JSC::LLInt::LLINT_SLOW_PATH_DECL):

• llint/LowLevelInterpreter.asm:
• llint/LowLevelInterpreter32_64.asm:
• llint/LowLevelInterpreter64.asm:
• runtime/Arguments.cpp:

(JSC::Arguments::deletePropertyByIndex):
(JSC::Arguments::defineOwnProperty):

• runtime/ArrayConstructor.cpp:
• runtime/ArrayConventions.h: Added.

(JSC):
(JSC::isDenseEnoughForVector):
(JSC::indexingHeaderForArray):
(JSC::baseIndexingHeaderForArray):

• runtime/ArrayPrototype.cpp:

(JSC::ArrayPrototype::create):
(JSC):
(JSC::ArrayPrototype::ArrayPrototype):
(JSC::arrayProtoFuncToString):
(JSC::arrayProtoFuncJoin):
(JSC::arrayProtoFuncSort):
(JSC::arrayProtoFuncFilter):
(JSC::arrayProtoFuncMap):
(JSC::arrayProtoFuncEvery):
(JSC::arrayProtoFuncForEach):
(JSC::arrayProtoFuncSome):
(JSC::arrayProtoFuncReduce):
(JSC::arrayProtoFuncReduceRight):

• runtime/ArrayPrototype.h:

(ArrayPrototype):
(JSC::ArrayPrototype::createStructure):

• runtime/ArrayStorage.h: Added.

(JSC):
(ArrayStorage):
(JSC::ArrayStorage::ArrayStorage):
(JSC::ArrayStorage::from):
(JSC::ArrayStorage::butterfly):
(JSC::ArrayStorage::indexingHeader):
(JSC::ArrayStorage::length):
(JSC::ArrayStorage::setLength):
(JSC::ArrayStorage::vectorLength):
(JSC::ArrayStorage::setVectorLength):
(JSC::ArrayStorage::copyHeaderFromDuringGC):
(JSC::ArrayStorage::inSparseMode):
(JSC::ArrayStorage::lengthOffset):
(JSC::ArrayStorage::vectorLengthOffset):
(JSC::ArrayStorage::numValuesInVectorOffset):
(JSC::ArrayStorage::vectorOffset):
(JSC::ArrayStorage::indexBiasOffset):
(JSC::ArrayStorage::sparseMapOffset):
(JSC::ArrayStorage::sizeFor):

• runtime/Butterfly.h: Added.

(JSC):
(Butterfly):
(JSC::Butterfly::Butterfly):
(JSC::Butterfly::totalSize):
(JSC::Butterfly::fromBase):
(JSC::Butterfly::offsetOfIndexingHeader):
(JSC::Butterfly::offsetOfPublicLength):
(JSC::Butterfly::offsetOfVectorLength):
(JSC::Butterfly::indexingHeader):
(JSC::Butterfly::propertyStorage):
(JSC::Butterfly::indexingPayload):
(JSC::Butterfly::arrayStorage):
(JSC::Butterfly::offsetOfPropertyStorage):
(JSC::Butterfly::indexOfPropertyStorage):
(JSC::Butterfly::base):

• runtime/ButterflyInlineMethods.h: Added.

(JSC):
(JSC::Butterfly::createUninitialized):
(JSC::Butterfly::create):
(JSC::Butterfly::createUninitializedDuringCollection):
(JSC::Butterfly::base):
(JSC::Butterfly::growPropertyStorage):
(JSC::Butterfly::growArrayRight):
(JSC::Butterfly::resizeArray):
(JSC::Butterfly::unshift):
(JSC::Butterfly::shift):

• runtime/ClassInfo.h:

(MethodTable):
(JSC):

• runtime/IndexingHeader.h: Added.

(JSC):
(IndexingHeader):
(JSC::IndexingHeader::offsetOfIndexingHeader):
(JSC::IndexingHeader::offsetOfPublicLength):
(JSC::IndexingHeader::offsetOfVectorLength):
(JSC::IndexingHeader::IndexingHeader):
(JSC::IndexingHeader::vectorLength):
(JSC::IndexingHeader::setVectorLength):
(JSC::IndexingHeader::publicLength):
(JSC::IndexingHeader::setPublicLength):
(JSC::IndexingHeader::from):
(JSC::IndexingHeader::fromEndOf):
(JSC::IndexingHeader::propertyStorage):
(JSC::IndexingHeader::arrayStorage):
(JSC::IndexingHeader::butterfly):

• runtime/IndexingHeaderInlineMethods.h: Added.

(JSC):
(JSC::IndexingHeader::preCapacity):
(JSC::IndexingHeader::indexingPayloadSizeInBytes):

• runtime/IndexingType.h: Added.

(JSC):
(JSC::hasIndexingHeader):

• runtime/JSActivation.cpp:

(JSC::JSActivation::JSActivation):
(JSC::JSActivation::visitChildren):
(JSC::JSActivation::getOwnNonIndexPropertyNames):

• runtime/JSActivation.h:

(JSActivation):
(JSC::JSActivation::tearOff):

• runtime/JSArray.cpp:

(JSC):
(JSC::createArrayButterflyInDictionaryIndexingMode):
(JSC::JSArray::setLengthWritable):
(JSC::JSArray::defineOwnProperty):
(JSC::JSArray::getOwnPropertySlot):
(JSC::JSArray::getOwnPropertyDescriptor):
(JSC::JSArray::put):
(JSC::JSArray::deleteProperty):
(JSC::JSArray::getOwnNonIndexPropertyNames):
(JSC::JSArray::unshiftCountSlowCase):
(JSC::JSArray::setLength):
(JSC::JSArray::pop):
(JSC::JSArray::push):
(JSC::JSArray::shiftCount):
(JSC::JSArray::unshiftCount):
(JSC::JSArray::sortNumeric):
(JSC::JSArray::sort):
(JSC::JSArray::fillArgList):
(JSC::JSArray::copyToArguments):
(JSC::JSArray::compactForSorting):

• runtime/JSArray.h:

(JSC):
(JSArray):
(JSC::JSArray::JSArray):
(JSC::JSArray::length):
(JSC::JSArray::createStructure):
(JSC::JSArray::isLengthWritable):
(JSC::createArrayButterfly):
(JSC::JSArray::create):
(JSC::JSArray::tryCreateUninitialized):

• runtime/JSBoundFunction.cpp:

(JSC::boundFunctionCall):
(JSC::boundFunctionConstruct):
(JSC::JSBoundFunction::finishCreation):

• runtime/JSCell.cpp:

(JSC::JSCell::getOwnNonIndexPropertyNames):
(JSC):

• runtime/JSCell.h:

(JSCell):

• runtime/JSFunction.cpp:

(JSC::JSFunction::getOwnPropertySlot):
(JSC::JSFunction::getOwnPropertyDescriptor):
(JSC::JSFunction::getOwnNonIndexPropertyNames):
(JSC::JSFunction::defineOwnProperty):

• runtime/JSFunction.h:

(JSFunction):

• runtime/JSGlobalData.cpp:

(JSC::JSGlobalData::JSGlobalData):

• runtime/JSGlobalData.h:

(JSGlobalData):

• runtime/JSGlobalObject.cpp:

(JSC::JSGlobalObject::reset):

• runtime/JSONObject.cpp:

(JSC::Stringifier::Holder::appendNextProperty):
(JSC::Walker::walk):

• runtime/JSObject.cpp:

(JSC):
(JSC::JSObject::visitButterfly):
(JSC::JSObject::visitChildren):
(JSC::JSFinalObject::visitChildren):
(JSC::JSObject::getOwnPropertySlotByIndex):
(JSC::JSObject::put):
(JSC::JSObject::putByIndex):
(JSC::JSObject::enterDictionaryIndexingModeWhenArrayStorageAlreadyExists):
(JSC::JSObject::enterDictionaryIndexingMode):
(JSC::JSObject::createArrayStorage):
(JSC::JSObject::createInitialArrayStorage):
(JSC::JSObject::ensureArrayStorageExistsAndEnterDictionaryIndexingMode):
(JSC::JSObject::putDirectAccessor):
(JSC::JSObject::deleteProperty):
(JSC::JSObject::deletePropertyByIndex):
(JSC::JSObject::getOwnPropertyNames):
(JSC::JSObject::getOwnNonIndexPropertyNames):
(JSC::JSObject::preventExtensions):
(JSC::JSObject::fillGetterPropertySlot):
(JSC::JSObject::putIndexedDescriptor):
(JSC::JSObject::defineOwnIndexedProperty):
(JSC::JSObject::allocateSparseIndexMap):
(JSC::JSObject::deallocateSparseIndexMap):
(JSC::JSObject::putByIndexBeyondVectorLengthWithArrayStorage):
(JSC::JSObject::putByIndexBeyondVectorLength):
(JSC::JSObject::putDirectIndexBeyondVectorLengthWithArrayStorage):
(JSC::JSObject::putDirectIndexBeyondVectorLength):
(JSC::JSObject::getNewVectorLength):
(JSC::JSObject::increaseVectorLength):
(JSC::JSObject::checkIndexingConsistency):
(JSC::JSObject::growOutOfLineStorage):
(JSC::JSObject::getOwnPropertyDescriptor):
(JSC::putDescriptor):
(JSC::JSObject::putDirectMayBeIndex):
(JSC::JSObject::defineOwnNonIndexProperty):
(JSC::JSObject::defineOwnProperty):
(JSC::JSObject::getOwnPropertySlotSlow):

• runtime/JSObject.h:

(JSC::JSObject::getArrayLength):
(JSObject):
(JSC::JSObject::getVectorLength):
(JSC::JSObject::putDirectIndex):
(JSC::JSObject::canGetIndexQuickly):
(JSC::JSObject::getIndexQuickly):
(JSC::JSObject::canSetIndexQuickly):
(JSC::JSObject::setIndexQuickly):
(JSC::JSObject::initializeIndex):
(JSC::JSObject::completeInitialization):
(JSC::JSObject::inSparseIndexingMode):
(JSC::JSObject::butterfly):
(JSC::JSObject::outOfLineStorage):
(JSC::JSObject::offsetForLocation):
(JSC::JSObject::indexingShouldBeSparse):
(JSC::JSObject::butterflyOffset):
(JSC::JSObject::butterflyAddress):
(JSC::JSObject::arrayStorage):
(JSC::JSObject::arrayStorageOrZero):
(JSC::JSObject::ensureArrayStorage):
(JSC::JSObject::checkIndexingConsistency):
(JSC::JSNonFinalObject::JSNonFinalObject):
(JSC):
(JSC::JSObject::setButterfly):
(JSC::JSObject::setButterflyWithoutChangingStructure):
(JSC::JSObject::JSObject):
(JSC::JSObject::inlineGetOwnPropertySlot):
(JSC::JSObject::putDirectInternal):
(JSC::JSObject::setStructureAndReallocateStorageIfNecessary):
(JSC::JSObject::putDirectWithoutTransition):
(JSC::offsetInButterfly):
(JSC::offsetRelativeToPatchedStorage):
(JSC::indexRelativeToBase):
(JSC::offsetRelativeToBase):

• runtime/JSPropertyNameIterator.cpp:

(JSC::JSPropertyNameIterator::create):

• runtime/JSSymbolTableObject.cpp:

(JSC::JSSymbolTableObject::getOwnNonIndexPropertyNames):

• runtime/JSSymbolTableObject.h:

(JSSymbolTableObject):

• runtime/JSTypeInfo.h:

(JSC):
(JSC::TypeInfo::interceptsGetOwnPropertySlotByIndexEvenWhenLengthIsNotZero):
(JSC::TypeInfo::overridesGetPropertyNames):

• runtime/LiteralParser.cpp:

(JSC::::parse):

• runtime/ObjectConstructor.cpp:
• runtime/ObjectPrototype.cpp:

(JSC::ObjectPrototype::ObjectPrototype):
(JSC):

• runtime/ObjectPrototype.h:

(ObjectPrototype):

• runtime/PropertyOffset.h:

(JSC::offsetInOutOfLineStorage):

• runtime/PropertyStorage.h: Added.

(JSC):

• runtime/PutDirectIndexMode.h: Added.

(JSC):

• runtime/RegExpMatchesArray.cpp:

(JSC::RegExpMatchesArray::RegExpMatchesArray):
(JSC):
(JSC::RegExpMatchesArray::create):
(JSC::RegExpMatchesArray::finishCreation):

• runtime/RegExpMatchesArray.h:

(RegExpMatchesArray):
(JSC::RegExpMatchesArray::createStructure):

• runtime/RegExpObject.cpp:

(JSC::RegExpObject::getOwnNonIndexPropertyNames):

• runtime/RegExpObject.h:

(RegExpObject):

• runtime/Reject.h: Added.

(JSC):
(JSC::reject):

• runtime/SparseArrayValueMap.cpp: Added.

(JSC):

• runtime/SparseArrayValueMap.h: Added.

(JSC):
(SparseArrayEntry):
(JSC::SparseArrayEntry::SparseArrayEntry):
(SparseArrayValueMap):
(JSC::SparseArrayValueMap::sparseMode):
(JSC::SparseArrayValueMap::setSparseMode):
(JSC::SparseArrayValueMap::lengthIsReadOnly):
(JSC::SparseArrayValueMap::setLengthIsReadOnly):
(JSC::SparseArrayValueMap::find):
(JSC::SparseArrayValueMap::remove):
(JSC::SparseArrayValueMap::notFound):
(JSC::SparseArrayValueMap::isEmpty):
(JSC::SparseArrayValueMap::contains):
(JSC::SparseArrayValueMap::size):
(JSC::SparseArrayValueMap::begin):
(JSC::SparseArrayValueMap::end):

• runtime/SparseArrayValueMapInlineMethods.h: Added.

(JSC):
(JSC::SparseArrayValueMap::SparseArrayValueMap):
(JSC::SparseArrayValueMap::~SparseArrayValueMap):
(JSC::SparseArrayValueMap::finishCreation):
(JSC::SparseArrayValueMap::create):
(JSC::SparseArrayValueMap::destroy):
(JSC::SparseArrayValueMap::createStructure):
(JSC::SparseArrayValueMap::add):
(JSC::SparseArrayValueMap::putEntry):
(JSC::SparseArrayValueMap::putDirect):
(JSC::SparseArrayEntry::get):
(JSC::SparseArrayEntry::getNonSparseMode):
(JSC::SparseArrayValueMap::visitChildren):

• runtime/StorageBarrier.h: Removed.
• runtime/StringObject.cpp:

(JSC::StringObject::putByIndex):
(JSC):
(JSC::StringObject::deletePropertyByIndex):

• runtime/StringObject.h:

(StringObject):

• runtime/StringPrototype.cpp:
• runtime/Structure.cpp:

(JSC::Structure::Structure):
(JSC::Structure::materializePropertyMap):
(JSC::Structure::nonPropertyTransition):
(JSC):

• runtime/Structure.h:

(Structure):
(JSC::Structure::indexingType):
(JSC::Structure::indexingTypeIncludingHistory):
(JSC::Structure::indexingTypeOffset):
(JSC::Structure::create):

• runtime/StructureTransitionTable.h:

(JSC):
(JSC::toAttributes):
(JSC::newIndexingType):
(JSC::StructureTransitionTable::Hash::hash):

• tests/mozilla/js1_6/Array/regress-304828.js:

Source/WebCore:

Teach the DOM that to intercept get/put on indexed properties, you now have
to override getOwnPropertySlotByIndex and putByIndex.

No new tests because no new behavior. One test was rebased because indexed
property iteration order now matches other engines (indexed properties always
come first).

• bindings/js/ArrayValue.cpp:

(WebCore::ArrayValue::get):

• bindings/js/JSBlobCustom.cpp:

(WebCore::JSBlobConstructor::constructJSBlob):

• bindings/js/JSCanvasRenderingContext2DCustom.cpp:

(WebCore::JSCanvasRenderingContext2D::setWebkitLineDash):

• bindings/js/JSDOMStringListCustom.cpp:

(WebCore::toDOMStringList):

• bindings/js/JSDOMStringMapCustom.cpp:

(WebCore::JSDOMStringMap::deletePropertyByIndex):
(WebCore):

• bindings/js/JSDOMWindowCustom.cpp:

(WebCore::JSDOMWindow::getOwnPropertySlot):
(WebCore::JSDOMWindow::getOwnPropertySlotByIndex):
(WebCore):
(WebCore::JSDOMWindow::putByIndex):
(WebCore::JSDOMWindow::deletePropertyByIndex):

• bindings/js/JSDOMWindowShell.cpp:

(WebCore::JSDOMWindowShell::getOwnPropertySlotByIndex):
(WebCore):
(WebCore::JSDOMWindowShell::putByIndex):
(WebCore::JSDOMWindowShell::deletePropertyByIndex):

• bindings/js/JSDOMWindowShell.h:

(JSDOMWindowShell):

• bindings/js/JSHistoryCustom.cpp:

(WebCore::JSHistory::deletePropertyByIndex):
(WebCore):

• bindings/js/JSInspectorFrontendHostCustom.cpp:

(WebCore::populateContextMenuItems):

• bindings/js/JSLocationCustom.cpp:

(WebCore::JSLocation::deletePropertyByIndex):
(WebCore):

• bindings/js/JSStorageCustom.cpp:

(WebCore::JSStorage::deletePropertyByIndex):
(WebCore):

• bindings/js/JSWebSocketCustom.cpp:

(WebCore::JSWebSocketConstructor::constructJSWebSocket):

• bindings/js/ScriptValue.cpp:

(WebCore::jsToInspectorValue):

• bindings/js/SerializedScriptValue.cpp:

(WebCore::CloneSerializer::serialize):

• bindings/scripts/CodeGeneratorJS.pm:

(GenerateHeader):
(GenerateImplementation):

• bridge/runtime_array.cpp:

(JSC::RuntimeArray::RuntimeArray):

• bridge/runtime_array.h:

(JSC::RuntimeArray::createStructure):
(RuntimeArray):

LayoutTests:

Modify the JSON test to indicate that iterating over properties now returns
indexed properties first. This is a behavior change that makes us more
compliant with other implementations.

Also check in new expected file for the edge cases of indexed property access
with prototype accessors. This changeset introduces a known regression in that
department, which is tracked here: ​https://bugs.webkit.org/show_bug.cgi?id=96596

• fast/js/resources/JSON-stringify.js:
• platform/mac/fast/js/primitive-property-access-edge-cases-expected.txt: Added.

Location:

trunk/Source/JavaScriptCore/runtime

Files:

• Arguments.cpp (modified) (2 diffs)
• ArrayConstructor.cpp (modified) (1 diff)
• ArrayConventions.h (added)
• ArrayPrototype.cpp (modified) (14 diffs)
• ArrayPrototype.h (modified) (2 diffs)
• ArrayStorage.h (added)
• Butterfly.h (added)
• ButterflyInlineMethods.h (added)
• ClassInfo.h (modified) (2 diffs)
• IndexingHeader.h (added)
• IndexingHeaderInlineMethods.h (added)
• IndexingType.h (added)
• JSActivation.cpp (modified) (2 diffs)
• JSActivation.h (modified) (1 diff)
• JSArray.cpp (modified) (30 diffs)
• JSArray.h (modified) (9 diffs)
• JSBoundFunction.cpp (modified) (3 diffs)
• JSCell.cpp (modified) (1 diff)
• JSCell.h (modified) (2 diffs)
• JSFunction.cpp (modified) (8 diffs)
• JSFunction.h (modified) (1 diff)
• JSGlobalData.cpp (modified) (2 diffs)
• JSGlobalData.h (modified) (1 diff)
• JSGlobalObject.cpp (modified) (1 diff)
• JSONObject.cpp (modified) (2 diffs)
• JSObject.cpp (modified) (28 diffs)
• JSObject.h (modified) (29 diffs)
• JSPropertyNameIterator.cpp (modified) (1 diff)
• JSSymbolTableObject.cpp (modified) (2 diffs)
• JSSymbolTableObject.h (modified) (1 diff)
• JSTypeInfo.h (modified) (2 diffs)
• LiteralParser.cpp (modified) (2 diffs)
• ObjectConstructor.cpp (modified) (1 diff)
• ObjectPrototype.cpp (modified) (2 diffs)
• ObjectPrototype.h (modified) (1 diff)
• PropertyOffset.h (modified) (1 diff)
• PropertyStorage.h (added)
• PutDirectIndexMode.h (added)
• RegExpMatchesArray.cpp (modified) (2 diffs)
• RegExpMatchesArray.h (modified) (3 diffs)
• RegExpObject.cpp (modified) (2 diffs)
• RegExpObject.h (modified) (1 diff)
• Reject.h (added)
• SparseArrayValueMap.cpp (added)
• SparseArrayValueMap.h (added)
• SparseArrayValueMapInlineMethods.h (added)
• StorageBarrier.h (deleted)
• StringObject.cpp (modified) (2 diffs)
• StringObject.h (modified) (2 diffs)
• StringPrototype.cpp (modified) (1 diff)
• Structure.cpp (modified) (5 diffs)
• Structure.h (modified) (9 diffs)
• StructureTransitionTable.h (modified) (3 diffs)

trunk/Source/JavaScriptCore/runtime/Arguments.cpp

@@ -256 +256 @@
     }
 
-    return JSObject::deleteProperty(thisObject, exec, Identifier(exec, String::number(i)));
+    return JSObject::deletePropertyByIndex(thisObject, exec, i);
 }
 
@@ -309 +309 @@
         PropertySlot slot;
         if ((!thisObject->d->deletedArguments || !thisObject->d->deletedArguments[i]) && !JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot))
-            object->putDirect(exec->globalData(), propertyName, thisObject->argument(i).get(), 0);
+            object->putDirectMayBeIndex(exec, propertyName, thisObject->argument(i).get());
         if (!Base::defineOwnProperty(object, exec, propertyName, descriptor, shouldThrow))
             return false;

trunk/Source/JavaScriptCore/runtime/ArrayConstructor.cpp

@@ -26 +26 @@
 
 #include "ArrayPrototype.h"
+#include "ButterflyInlineMethods.h"
+#include "CopiedSpaceInlineMethods.h"
 #include "Error.h"
 #include "ExceptionHelpers.h"

trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp

@@ -25 +25 @@
 #include "ArrayPrototype.h"
 
+#include "ButterflyInlineMethods.h"
 #include "CachedCall.h"
 #include "CodeBlock.h"
+#include "CopiedSpaceInlineMethods.h"
 #include "Interpreter.h"
 #include "JIT.h"
@@ -115 +117 @@
 */
 
+ArrayPrototype* ArrayPrototype::create(ExecState* exec, JSGlobalObject* globalObject, Structure* structure)
+{
+    Butterfly* butterfly = createArrayButterfly(exec->globalData(), 0);
+    ArrayPrototype* prototype = new (NotNull, allocateCell<ArrayPrototype>(*exec->heap())) ArrayPrototype(globalObject, structure, butterfly);
+    prototype->finishCreation(globalObject);
+    return prototype;
+}
+
 // ECMA 15.4.4
-ArrayPrototype::ArrayPrototype(JSGlobalObject* globalObject, Structure* structure)
-    : JSArray(globalObject->globalData(), structure)
+ArrayPrototype::ArrayPrototype(JSGlobalObject* globalObject, Structure* structure, Butterfly* butterfly)
+    : JSArray(globalObject->globalData(), structure, butterfly)
 {
 }
@@ -293 +303 @@
     for (unsigned k = 0; k < length; k++) {
         JSValue element;
-        if (thisObj->canGetIndex(k))
-            element = thisObj->getIndex(k);
+        if (thisObj->canGetIndexQuickly(k))
+            element = thisObj->getIndexQuickly(k);
         else
             element = thisObj->get(exec, k);
@@ -414 +424 @@
 
         for (; k < length; k++) {
-            if (!array->canGetIndex(k))
+            if (!array->canGetIndexQuickly(k))
                 break;
 
-            JSValue element = array->getIndex(k);
+            JSValue element = array->getIndexQuickly(k);
             if (!element.isUndefinedOrNull())
                 stringJoiner.append(element.toWTFStringInline(exec));
@@ -629 +639 @@
     CallType callType = getCallData(function, callData);
 
-    if (thisObj->classInfo() == &JSArray::s_info && !asArray(thisObj)->inSparseMode()) {
+    if (thisObj->classInfo() == &JSArray::s_info && !asArray(thisObj)->inSparseIndexingMode()) {
         if (isNumericCompareFunction(exec, callType, callData))
             asArray(thisObj)->sortNumeric(exec, function, callType, callData);
@@ -789 +799 @@
         CachedCall cachedCall(exec, f, 3);
         for (; k < length && !exec->hadException(); ++k) {
-            if (!array->canGetIndex(k))
+            if (!array->canGetIndexQuickly(k))
                 break;
-            JSValue v = array->getIndex(k);
+            JSValue v = array->getIndexQuickly(k);
             cachedCall.setThis(applyThis);
             cachedCall.setArgument(0, v);
@@ -847 +857 @@
         CachedCall cachedCall(exec, f, 3);
         for (; k < length && !exec->hadException(); ++k) {
-            if (UNLIKELY(!array->canGetIndex(k)))
+            if (UNLIKELY(!array->canGetIndexQuickly(k)))
                 break;
 
             cachedCall.setThis(applyThis);
-            cachedCall.setArgument(0, array->getIndex(k));
+            cachedCall.setArgument(0, array->getIndexQuickly(k));
             cachedCall.setArgument(1, jsNumber(k));
             cachedCall.setArgument(2, thisObj);
@@ -910 +920 @@
         CachedCall cachedCall(exec, f, 3);
         for (; k < length && !exec->hadException(); ++k) {
-            if (UNLIKELY(!array->canGetIndex(k)))
+            if (UNLIKELY(!array->canGetIndexQuickly(k)))
                 break;
             
             cachedCall.setThis(applyThis);
-            cachedCall.setArgument(0, array->getIndex(k));
+            cachedCall.setArgument(0, array->getIndexQuickly(k));
             cachedCall.setArgument(1, jsNumber(k));
             cachedCall.setArgument(2, thisObj);
@@ -966 +976 @@
         CachedCall cachedCall(exec, f, 3);
         for (; k < length && !exec->hadException(); ++k) {
-            if (UNLIKELY(!array->canGetIndex(k)))
+            if (UNLIKELY(!array->canGetIndexQuickly(k)))
                 break;
 
             cachedCall.setThis(applyThis);
-            cachedCall.setArgument(0, array->getIndex(k));
+            cachedCall.setArgument(0, array->getIndexQuickly(k));
             cachedCall.setArgument(1, jsNumber(k));
             cachedCall.setArgument(2, thisObj);
@@ -1018 +1028 @@
         CachedCall cachedCall(exec, f, 3);
         for (; k < length && !exec->hadException(); ++k) {
-            if (UNLIKELY(!array->canGetIndex(k)))
+            if (UNLIKELY(!array->canGetIndexQuickly(k)))
                 break;
             
             cachedCall.setThis(applyThis);
-            cachedCall.setArgument(0, array->getIndex(k));
+            cachedCall.setArgument(0, array->getIndexQuickly(k));
             cachedCall.setArgument(1, jsNumber(k));
             cachedCall.setArgument(2, thisObj);
@@ -1076 +1086 @@
     if (exec->argumentCount() >= 2)
         rv = exec->argument(1);
-    else if (array && array->canGetIndex(0)){
-        rv = array->getIndex(0);
+    else if (array && array->canGetIndexQuickly(0)) {
+        rv = array->getIndexQuickly(0);
         i = 1;
     } else {
@@ -1098 +1108 @@
             cachedCall.setArgument(0, rv);
             JSValue v;
-            if (LIKELY(array->canGetIndex(i)))
-                v = array->getIndex(i);
+            if (LIKELY(array->canGetIndexQuickly(i)))
+                v = array->getIndexQuickly(i);
             else
                 break; // length has been made unsafe while we enumerate fallback to slow path
@@ -1153 +1163 @@
     if (exec->argumentCount() >= 2)
         rv = exec->argument(1);
-    else if (array && array->canGetIndex(length - 1)){
-        rv = array->getIndex(length - 1);
+    else if (array && array->canGetIndexQuickly(length - 1)) {
+        rv = array->getIndexQuickly(length - 1);
         i = 1;
     } else {
@@ -1175 +1185 @@
             cachedCall.setThis(jsUndefined());
             cachedCall.setArgument(0, rv);
-            if (UNLIKELY(!array->canGetIndex(idx)))
+            if (UNLIKELY(!array->canGetIndexQuickly(idx)))
                 break; // length has been made unsafe while we enumerate fallback to slow path
-            cachedCall.setArgument(1, array->getIndex(idx));
+            cachedCall.setArgument(1, array->getIndexQuickly(idx));
             cachedCall.setArgument(2, jsNumber(idx));
             cachedCall.setArgument(3, array);

trunk/Source/JavaScriptCore/runtime/ArrayPrototype.h

@@ -29 +29 @@
     class ArrayPrototype : public JSArray {
     private:
-        ArrayPrototype(JSGlobalObject*, Structure*);
+        ArrayPrototype(JSGlobalObject*, Structure*, Butterfly*);
 
     public:
         typedef JSArray Base;
 
-        static ArrayPrototype* create(ExecState* exec, JSGlobalObject* globalObject, Structure* structure)
-        {
-            ArrayPrototype* prototype = new (NotNull, allocateCell<ArrayPrototype>(*exec->heap())) ArrayPrototype(globalObject, structure);
-            prototype->finishCreation(globalObject);
-            return prototype;
-        }
+        static ArrayPrototype* create(ExecState*, JSGlobalObject*, Structure*);
         
         static bool getOwnPropertySlot(JSCell*, ExecState*, PropertyName, PropertySlot&);
@@ -48 +43 @@
         static Structure* createStructure(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype)
         {
-            return Structure::create(globalData, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), &s_info);
+            return Structure::create(globalData, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), &s_info, ArrayWithArrayStorage);
         }
 

trunk/Source/JavaScriptCore/runtime/ClassInfo.h

@@ -73 +73 @@
         GetOwnPropertyNamesFunctionPtr getOwnPropertyNames;
 
+        typedef void (*GetOwnNonIndexPropertyNamesFunctionPtr)(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
+        GetOwnNonIndexPropertyNamesFunctionPtr getOwnNonIndexPropertyNames;
+
         typedef void (*GetPropertyNamesFunctionPtr)(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
         GetPropertyNamesFunctionPtr getPropertyNames;
@@ -125 +128 @@
         &ClassName::defaultValue, \
         &ClassName::getOwnPropertyNames, \
+        &ClassName::getOwnNonIndexPropertyNames, \
         &ClassName::getPropertyNames, \
         &ClassName::className, \

trunk/Source/JavaScriptCore/runtime/JSActivation.cpp

@@ -108 +108 @@
 }
 
-void JSActivation::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
+void JSActivation::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
 {
     JSActivation* thisObject = jsCast<JSActivation*>(object);
@@ -123 +123 @@
         propertyNames.add(Identifier(exec, it->first.get()));
     }
-    // Skip the JSVariableObject implementation of getOwnPropertyNames
-    JSObject::getOwnPropertyNames(thisObject, exec, propertyNames, mode);
+    // Skip the JSVariableObject implementation of getOwnNonIndexPropertyNames
+    JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode);
 }
 

trunk/Source/JavaScriptCore/runtime/JSActivation.h

@@ -66 +66 @@
 
         static bool getOwnPropertySlot(JSCell*, ExecState*, PropertyName, PropertySlot&);
-        static void getOwnPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
+        static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
         JS_EXPORT_PRIVATE static bool getOwnPropertyDescriptor(JSObject*, ExecState*, PropertyName, PropertyDescriptor&);
 

trunk/Source/JavaScriptCore/runtime/JSArray.cpp

@@ -1 +1 @@
 /*
  *  Copyright (C) 1999-2000 Harri Porten ([email protected])
- *  Copyright (C) 2003, 2007, 2008, 2009 Apple Inc. All rights reserved.
+ *  Copyright (C) 2003, 2007, 2008, 2009, 2012 Apple Inc. All rights reserved.
  *  Copyright (C) 2003 Peter Kelly ([email protected])
  *  Copyright (C) 2006 Alexey Proskuryakov ([email protected])
@@ -25 +25 @@
 
 #include "ArrayPrototype.h"
+#include "ButterflyInlineMethods.h"
 #include "CopiedSpace.h"
 #include "CopiedSpaceInlineMethods.h"
@@ -31 +32 @@
 #include "Executable.h"
 #include "GetterSetter.h"
+#include "IndexingHeaderInlineMethods.h"
 #include "PropertyNameArray.h"
+#include "Reject.h"
+#include "SparseArrayValueMapInlineMethods.h"
 #include <wtf/AVLTree.h>
 #include <wtf/Assertions.h>
@@ -46 +50 @@
 ASSERT_HAS_TRIVIAL_DESTRUCTOR(JSArray);
 
-// Overview of JSArray
-//
-// Properties of JSArray objects may be stored in one of three locations:
-//   * The regular JSObject property map.
-//   * A storage vector.
-//   * A sparse map of array entries.
-//
-// Properties with non-numeric identifiers, with identifiers that are not representable
-// as an unsigned integer, or where the value is greater than  MAX_ARRAY_INDEX
-// (specifically, this is only one property - the value 0xFFFFFFFFU as an unsigned 32-bit
-// integer) are not considered array indices and will be stored in the JSObject property map.
-//
-// All properties with a numeric identifer, representable as an unsigned integer i,
-// where (i <= MAX_ARRAY_INDEX), are an array index and will be stored in either the
-// storage vector or the sparse map.  An array index i will be handled in the following
-// fashion:
-//
-//   * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector,
-//     unless the array is in SparseMode in which case all properties go into the map.
-//   * Where (MIN_SPARSE_ARRAY_INDEX <= i <= MAX_STORAGE_VECTOR_INDEX) the value will either
-//     be stored in the storage vector or in the sparse array, depending on the density of
-//     data that would be stored in the vector (a vector being used where at least
-//     (1 / minDensityMultiplier) of the entries would be populated).
-//   * Where (MAX_STORAGE_VECTOR_INDEX < i <= MAX_ARRAY_INDEX) the value will always be stored
-//     in the sparse array.
-
-// The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
-// function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
-// size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) +
-// (vectorLength * sizeof(WriteBarrier<Unknown>)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
-#define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>))
-
-// These values have to be macros to be used in max() and min() without introducing
-// a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
-#define MIN_SPARSE_ARRAY_INDEX 10000U
-#define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
-// 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
-#define MAX_ARRAY_INDEX 0xFFFFFFFEU
-
-// The value BASE_VECTOR_LEN is the maximum number of vector elements we'll allocate
-// for an array that was created with a sepcified length (e.g. a = new Array(123))
-#define BASE_VECTOR_LEN 4U
-    
-// The upper bound to the size we'll grow a zero length array when the first element
-// is added.
-#define FIRST_VECTOR_GROW 4U
-
-// Our policy for when to use a vector and when to use a sparse map.
-// For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
-// When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
-// as long as it is 1/8 full. If more sparse than that, we use a map.
-static const unsigned minDensityMultiplier = 8;
-
 const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0, CREATE_METHOD_TABLE(JSArray)};
 
-// We keep track of the size of the last array after it was grown.  We use this
-// as a simple heuristic for as the value to grow the next array from size 0.
-// This value is capped by the constant FIRST_VECTOR_GROW defined above.
-static unsigned lastArraySize = 0;
-
-static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
-{
-    return length <= MIN_SPARSE_ARRAY_INDEX || length / minDensityMultiplier <= numValues;
-}
-
-static bool reject(ExecState* exec, bool throwException, const char* message)
-{
-    if (throwException)
-        throwTypeError(exec, ASCIILiteral(message));
-    return false;
-}
-
-#if !CHECK_ARRAY_CONSISTENCY
-
-inline void JSArray::checkConsistency(ConsistencyCheckType)
-{
-}
-
+Butterfly* createArrayButterflyInDictionaryIndexingMode(JSGlobalData& globalData, unsigned initialLength)
+{
+    Butterfly* butterfly = Butterfly::create(
+        globalData, 0, 0, true, IndexingHeader(), ArrayStorage::sizeFor(0));
+    ArrayStorage* storage = butterfly->arrayStorage();
+    storage->setLength(initialLength);
+    storage->setVectorLength(0);
+    storage->m_indexBias = 0;
+    storage->m_sparseMap.clear();
+    storage->m_numValuesInVector = 0;
+#if CHECK_ARRAY_CONSISTENCY
+    storage->m_initializationIndex = 0;
+    storage->m_inCompactInitialization = 0;
 #endif
-
-void JSArray::finishCreation(JSGlobalData& globalData, unsigned initialLength)
-{
-    Base::finishCreation(globalData);
-    ASSERT(inherits(&s_info));
-
-    unsigned initialVectorLength = BASE_VECTOR_LEN;
-    unsigned initialStorageSize = storageSize(initialVectorLength);
-
-    void* newStorage = 0;
-    if (!globalData.heap.tryAllocateStorage(initialStorageSize, &newStorage))
-        CRASH();
-    
-    m_storage = static_cast<ArrayStorage*>(newStorage);
-    m_storage->m_allocBase = m_storage;
-    m_storage->m_length = initialLength;
-    m_vectorLength = initialVectorLength;
-    m_storage->m_numValuesInVector = 0;
-#if CHECK_ARRAY_CONSISTENCY
-    m_storage->m_inCompactInitialization = false;
-#endif
-
-    checkConsistency();
-}
-
-JSArray* JSArray::tryFinishCreationUninitialized(JSGlobalData& globalData, unsigned initialLength)
-{
-    Base::finishCreation(globalData);
-    ASSERT(inherits(&s_info));
-
-    // Check for lengths larger than we can handle with a vector.
-    if (initialLength > MAX_STORAGE_VECTOR_LENGTH)
-        return 0;
-
-    unsigned initialVectorLength = max(initialLength, BASE_VECTOR_LEN);
-    unsigned initialStorageSize = storageSize(initialVectorLength);
-
-    void* newStorage = 0;
-    if (!globalData.heap.tryAllocateStorage(initialStorageSize, &newStorage))
-        CRASH();
-    
-    m_storage = static_cast<ArrayStorage*>(newStorage);
-    m_storage->m_allocBase = m_storage;
-    m_storage->m_length = initialLength;
-    m_vectorLength = initialVectorLength;
-    m_storage->m_numValuesInVector = initialLength;
-
-#if CHECK_ARRAY_CONSISTENCY
-    m_storage->m_initializationIndex = 0;
-    m_storage->m_inCompactInitialization = true;
-#endif
-
-    return this;
-}
-
-// This function can be called multiple times on the same object.
-void JSArray::finalize(JSCell* cell)
-{
-    JSArray* thisObject = jsCast<JSArray*>(cell);
-    thisObject->checkConsistency(DestructorConsistencyCheck);
-    thisObject->deallocateSparseMap();
-}
-
-inline SparseArrayValueMap::AddResult SparseArrayValueMap::add(JSArray* array, unsigned i)
-{
-    SparseArrayEntry entry;
-    entry.setWithoutWriteBarrier(jsUndefined());
-
-    AddResult result = m_map.add(i, entry);
-    size_t capacity = m_map.capacity();
-    if (capacity != m_reportedCapacity) {
-        Heap::heap(array)->reportExtraMemoryCost((capacity - m_reportedCapacity) * (sizeof(unsigned) + sizeof(WriteBarrier<Unknown>)));
-        m_reportedCapacity = capacity;
-    }
-    return result;
-}
-
-inline void SparseArrayValueMap::put(ExecState* exec, JSArray* array, unsigned i, JSValue value, bool shouldThrow)
-{
-    AddResult result = add(array, i);
-    SparseArrayEntry& entry = result.iterator->second;
-
-    // To save a separate find & add, we first always add to the sparse map.
-    // In the uncommon case that this is a new property, and the array is not
-    // extensible, this is not the right thing to have done - so remove again.
-    if (result.isNewEntry && !array->isExtensible()) {
-        remove(result.iterator);
-        if (shouldThrow)
-            throwTypeError(exec, ASCIILiteral(StrictModeReadonlyPropertyWriteError));
-        return;
-    }
-
-    if (!(entry.attributes & Accessor)) {
-        if (entry.attributes & ReadOnly) {
-            if (shouldThrow)
-                throwTypeError(exec, ASCIILiteral(StrictModeReadonlyPropertyWriteError));
-            return;
-        }
-
-        entry.set(exec->globalData(), array, value);
-        return;
-    }
-
-    JSValue accessor = entry.Base::get();
-    ASSERT(accessor.isGetterSetter());
-    JSObject* setter = asGetterSetter(accessor)->setter();
-    
-    if (!setter) {
-        if (shouldThrow)
-            throwTypeError(exec, ASCIILiteral(StrictModeReadonlyPropertyWriteError));
-        return;
-    }
-
-    CallData callData;
-    CallType callType = setter->methodTable()->getCallData(setter, callData);
-    MarkedArgumentBuffer args;
-    args.append(value);
-    call(exec, setter, callType, callData, array, args);
-}
-
-inline bool SparseArrayValueMap::putDirect(ExecState* exec, JSArray* array, unsigned i, JSValue value, PutDirectIndexMode mode)
-{
-    AddResult result = add(array, i);
-    SparseArrayEntry& entry = result.iterator->second;
-
-    // To save a separate find & add, we first always add to the sparse map.
-    // In the uncommon case that this is a new property, and the array is not
-    // extensible, this is not the right thing to have done - so remove again.
-    if (mode != PutDirectIndexLikePutDirect && result.isNewEntry && !array->isExtensible()) {
-        remove(result.iterator);
-        return reject(exec, mode == PutDirectIndexShouldThrow, "Attempting to define property on object that is not extensible.");
-    }
-
-    entry.attributes = 0;
-    entry.set(exec->globalData(), array, value);
-    return true;
-}
-
-inline void SparseArrayEntry::get(PropertySlot& slot) const
-{
-    JSValue value = Base::get();
-    ASSERT(value);
-
-    if (LIKELY(!value.isGetterSetter())) {
-        slot.setValue(value);
-        return;
-    }
-
-    JSObject* getter = asGetterSetter(value)->getter();
-    if (!getter) {
-        slot.setUndefined();
-        return;
-    }
-
-    slot.setGetterSlot(getter);
-}
-
-inline void SparseArrayEntry::get(PropertyDescriptor& descriptor) const
-{
-    descriptor.setDescriptor(Base::get(), attributes);
-}
-
-inline JSValue SparseArrayEntry::get(ExecState* exec, JSArray* array) const
-{
-    JSValue result = Base::get();
-    ASSERT(result);
-
-    if (LIKELY(!result.isGetterSetter()))
-        return result;
-
-    JSObject* getter = asGetterSetter(result)->getter();
-    if (!getter)
-        return jsUndefined();
-
-    CallData callData;
-    CallType callType = getter->methodTable()->getCallData(getter, callData);
-    return call(exec, getter, callType, callData, array, exec->emptyList());
-}
-
-inline JSValue SparseArrayEntry::getNonSparseMode() const
-{
-    ASSERT(!attributes);
-    return Base::get();
-}
-
-inline void SparseArrayValueMap::visitChildren(SlotVisitor& visitor)
-{
-    iterator end = m_map.end();
-    for (iterator it = m_map.begin(); it != end; ++it)
-        visitor.append(&it->second);
-}
-
-void JSArray::allocateSparseMap(JSGlobalData& globalData)
-{
-    m_sparseValueMap = new SparseArrayValueMap;
-    globalData.heap.addFinalizer(this, finalize);
-}
-
-void JSArray::deallocateSparseMap()
-{
-    delete m_sparseValueMap;
-    m_sparseValueMap = 0;
-}
-
-void JSArray::enterDictionaryMode(JSGlobalData& globalData)
-{
-    ArrayStorage* storage = m_storage;
-    SparseArrayValueMap* map = m_sparseValueMap;
-
-    if (!map) {
-        allocateSparseMap(globalData);
-        map = m_sparseValueMap;
-    }
-
-    if (map->sparseMode())
-        return;
-
-    map->setSparseMode();
-
-    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
-    for (unsigned i = 0; i < usedVectorLength; ++i) {
-        JSValue value = storage->m_vector[i].get();
-        // This will always be a new entry in the map, so no need to check we can write,
-        // and attributes are default so no need to set them.
-        if (value)
-            map->add(this, i).iterator->second.set(globalData, this, value);
-    }
-
-    void* newRawStorage = 0;
-    if (!globalData.heap.tryAllocateStorage(storageSize(0), &newRawStorage))
-        CRASH();
-    
-    ArrayStorage* newStorage = static_cast<ArrayStorage*>(newRawStorage);
-    memcpy(newStorage, m_storage, storageSize(0));
-    newStorage->m_allocBase = newStorage;
-    m_storage = newStorage;
-    m_indexBias = 0;
-    m_vectorLength = 0;
-}
-
-void JSArray::putDescriptor(ExecState* exec, SparseArrayEntry* entryInMap, PropertyDescriptor& descriptor, PropertyDescriptor& oldDescriptor)
-{
-    if (descriptor.isDataDescriptor()) {
-        if (descriptor.value())
-            entryInMap->set(exec->globalData(), this, descriptor.value());
-        else if (oldDescriptor.isAccessorDescriptor())
-            entryInMap->set(exec->globalData(), this, jsUndefined());
-        entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor) & ~Accessor;
-        return;
-    }
-
-    if (descriptor.isAccessorDescriptor()) {
-        JSObject* getter = 0;
-        if (descriptor.getterPresent())
-            getter = descriptor.getterObject();
-        else if (oldDescriptor.isAccessorDescriptor())
-            getter = oldDescriptor.getterObject();
-        JSObject* setter = 0;
-        if (descriptor.setterPresent())
-            setter = descriptor.setterObject();
-        else if (oldDescriptor.isAccessorDescriptor())
-            setter = oldDescriptor.setterObject();
-
-        GetterSetter* accessor = GetterSetter::create(exec);
-        if (getter)
-            accessor->setGetter(exec->globalData(), getter);
-        if (setter)
-            accessor->setSetter(exec->globalData(), setter);
-
-        entryInMap->set(exec->globalData(), this, accessor);
-        entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor) & ~ReadOnly;
-        return;
-    }
-
-    ASSERT(descriptor.isGenericDescriptor());
-    entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor);
-}
-
-// Defined in ES5.1 8.12.9
-bool JSArray::defineOwnNumericProperty(ExecState* exec, unsigned index, PropertyDescriptor& descriptor, bool throwException)
-{
-    ASSERT(index != 0xFFFFFFFF);
-
-    if (!inSparseMode()) {
-        // Fast case: we're putting a regular property to a regular array
-        // FIXME: this will pessimistically assume that if attributes are missing then they'll default to false
-        // – however if the property currently exists missing attributes will override from their current 'true'
-        // state (i.e. defineOwnProperty could be used to set a value without needing to entering 'SparseMode').
-        if (!descriptor.attributes()) {
-            ASSERT(!descriptor.isAccessorDescriptor());
-            return putDirectIndex(exec, index, descriptor.value(), throwException ? PutDirectIndexShouldThrow : PutDirectIndexShouldNotThrow);
-        }
-
-        enterDictionaryMode(exec->globalData());
-    }
-
-    SparseArrayValueMap* map = m_sparseValueMap;
-    ASSERT(map);
-
-    // 1. Let current be the result of calling the [[GetOwnProperty]] internal method of O with property name P.
-    SparseArrayValueMap::AddResult result = map->add(this, index);
-    SparseArrayEntry* entryInMap = &result.iterator->second;
-
-    // 2. Let extensible be the value of the [[Extensible]] internal property of O.
-    // 3. If current is undefined and extensible is false, then Reject.
-    // 4. If current is undefined and extensible is true, then
-    if (result.isNewEntry) {
-        if (!isExtensible()) {
-            map->remove(result.iterator);
-            return reject(exec, throwException, "Attempting to define property on object that is not extensible.");
-        }
-
-        // 4.a. If IsGenericDescriptor(Desc) or IsDataDescriptor(Desc) is true, then create an own data property
-        // named P of object O whose [[Value]], [[Writable]], [[Enumerable]] and [[Configurable]] attribute values
-        // are described by Desc. If the value of an attribute field of Desc is absent, the attribute of the newly
-        // created property is set to its default value.
-        // 4.b. Else, Desc must be an accessor Property Descriptor so, create an own accessor property named P of
-        // object O whose [[Get]], [[Set]], [[Enumerable]] and [[Configurable]] attribute values are described by
-        // Desc. If the value of an attribute field of Desc is absent, the attribute of the newly created property
-        // is set to its default value.
-        // 4.c. Return true.
-
-        PropertyDescriptor defaults;
-        entryInMap->setWithoutWriteBarrier(jsUndefined());
-        entryInMap->attributes = DontDelete | DontEnum | ReadOnly;
-        entryInMap->get(defaults);
-
-        putDescriptor(exec, entryInMap, descriptor, defaults);
-        if (index >= m_storage->m_length)
-            m_storage->m_length = index + 1;
-        return true;
-    }
-
-    // 5. Return true, if every field in Desc is absent.
-    // 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).
-    PropertyDescriptor current;
-    entryInMap->get(current);
-    if (descriptor.isEmpty() || descriptor.equalTo(exec, current))
-        return true;
-
-    // 7. If the [[Configurable]] field of current is false then
-    if (!current.configurable()) {
-        // 7.a. Reject, if the [[Configurable]] field of Desc is true.
-        if (descriptor.configurablePresent() && descriptor.configurable())
-            return reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property.");
-        // 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.
-        if (descriptor.enumerablePresent() && current.enumerable() != descriptor.enumerable())
-            return reject(exec, throwException, "Attempting to change enumerable attribute of unconfigurable property.");
-    }
-
-    // 8. If IsGenericDescriptor(Desc) is true, then no further validation is required.
-    if (!descriptor.isGenericDescriptor()) {
-        // 9. Else, if IsDataDescriptor(current) and IsDataDescriptor(Desc) have different results, then
-        if (current.isDataDescriptor() != descriptor.isDataDescriptor()) {
-            // 9.a. Reject, if the [[Configurable]] field of current is false.
-            if (!current.configurable())
-                return reject(exec, throwException, "Attempting to change access mechanism for an unconfigurable property.");
-            // 9.b. If IsDataDescriptor(current) is true, then convert the property named P of object O from a
-            // data property to an accessor property. Preserve the existing values of the converted property‘s
-            // [[Configurable]] and [[Enumerable]] attributes and set the rest of the property‘s attributes to
-            // their default values.
-            // 9.c. Else, convert the property named P of object O from an accessor property to a data property.
-            // Preserve the existing values of the converted property‘s [[Configurable]] and [[Enumerable]]
-            // attributes and set the rest of the property‘s attributes to their default values.
-        } else if (current.isDataDescriptor() && descriptor.isDataDescriptor()) {
-            // 10. Else, if IsDataDescriptor(current) and IsDataDescriptor(Desc) are both true, then
-            // 10.a. If the [[Configurable]] field of current is false, then
-            if (!current.configurable() && !current.writable()) {
-                // 10.a.i. Reject, if the [[Writable]] field of current is false and the [[Writable]] field of Desc is true.
-                if (descriptor.writable())
-                    return reject(exec, throwException, "Attempting to change writable attribute of unconfigurable property.");
-                // 10.a.ii. If the [[Writable]] field of current is false, then
-                // 10.a.ii.1. Reject, if the [[Value]] field of Desc is present and SameValue(Desc.[[Value]], current.[[Value]]) is false.
-                if (descriptor.value() && !sameValue(exec, descriptor.value(), current.value()))
-                    return reject(exec, throwException, "Attempting to change value of a readonly property.");
-            }
-            // 10.b. else, the [[Configurable]] field of current is true, so any change is acceptable.
-        } else {
-            ASSERT(current.isAccessorDescriptor() && current.getterPresent() && current.setterPresent());
-            // 11. Else, IsAccessorDescriptor(current) and IsAccessorDescriptor(Desc) are both true so, if the [[Configurable]] field of current is false, then
-            if (!current.configurable()) {
-                // 11.i. Reject, if the [[Set]] field of Desc is present and SameValue(Desc.[[Set]], current.[[Set]]) is false.
-                if (descriptor.setterPresent() && descriptor.setter() != current.setter())
-                    return reject(exec, throwException, "Attempting to change the setter of an unconfigurable property.");
-                // 11.ii. Reject, if the [[Get]] field of Desc is present and SameValue(Desc.[[Get]], current.[[Get]]) is false.
-                if (descriptor.getterPresent() && descriptor.getter() != current.getter())
-                    return reject(exec, throwException, "Attempting to change the getter of an unconfigurable property.");
-            }
-        }
-    }
-
-    // 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.
-    putDescriptor(exec, entryInMap, descriptor, current);
-    // 13. Return true.
-    return true;
+    return butterfly;
 }
 
@@ -528 +75 @@
         return;
 
-    enterDictionaryMode(exec->globalData());
-
-    SparseArrayValueMap* map = m_sparseValueMap;
+    enterDictionaryIndexingMode(exec->globalData());
+
+    SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get();
     ASSERT(map);
     map->setLengthIsReadOnly();
@@ -631 +178 @@
         // 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.
         // f. Return true.
-        return array->defineOwnNumericProperty(exec, index, descriptor, throwException);
-    }
-
-    return JSObject::defineOwnProperty(object, exec, propertyName, descriptor, throwException);
-}
-
-bool JSArray::getOwnPropertySlotByIndex(JSCell* cell, ExecState* exec, unsigned i, PropertySlot& slot)
-{
-    JSArray* thisObject = jsCast<JSArray*>(cell);
-    ArrayStorage* storage = thisObject->m_storage;
-
-    if (i >= storage->m_length) {
-        if (i > MAX_ARRAY_INDEX)
-            return thisObject->methodTable()->getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
-        return false;
-    }
-
-    if (i < thisObject->m_vectorLength) {
-        JSValue value = storage->m_vector[i].get();
-        if (value) {
-            slot.setValue(value);
-            return true;
-        }
-    } else if (SparseArrayValueMap* map = thisObject->m_sparseValueMap) {
-        SparseArrayValueMap::iterator it = map->find(i);
-        if (it != map->notFound()) {
-            it->second.get(slot);
-            return true;
-        }
-    }
-
-    return JSObject::getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
+        return array->defineOwnIndexedProperty(exec, index, descriptor, throwException);
+    }
+
+    return array->JSObject::defineOwnNonIndexProperty(exec, propertyName, descriptor, throwException);
 }
 
@@ -673 +192 @@
     }
 
-    unsigned i = propertyName.asIndex();
-    if (i != PropertyName::NotAnIndex)
-        return JSArray::getOwnPropertySlotByIndex(thisObject, exec, i, slot);
-
     return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
 }
@@ -688 +203 @@
     }
 
-    ArrayStorage* storage = thisObject->m_storage;
-    
-    unsigned i = propertyName.asIndex();
-    if (i != PropertyName::NotAnIndex) {
-        if (i >= storage->m_length)
-            return false;
-        if (i < thisObject->m_vectorLength) {
-            WriteBarrier<Unknown>& value = storage->m_vector[i];
-            if (value) {
-                descriptor.setDescriptor(value.get(), 0);
-                return true;
-            }
-        } else if (SparseArrayValueMap* map = thisObject->m_sparseValueMap) {
-            SparseArrayValueMap::iterator it = map->find(i);
-            if (it != map->notFound()) {
-                it->second.get(descriptor);
-                return true;
-            }
-        }
-    }
     return JSObject::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor);
 }
@@ -715 +210 @@
 {
     JSArray* thisObject = jsCast<JSArray*>(cell);
-    unsigned i = propertyName.asIndex();
-    if (i != PropertyName::NotAnIndex) {
-        putByIndex(thisObject, exec, i, value, slot.isStrictMode());
-        return;
-    }
 
     if (propertyName == exec->propertyNames().length) {
@@ -734 +224 @@
 }
 
-void JSArray::putByIndex(JSCell* cell, ExecState* exec, unsigned i, JSValue value, bool shouldThrow)
+bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, PropertyName propertyName)
 {
     JSArray* thisObject = jsCast<JSArray*>(cell);
-    thisObject->checkConsistency();
-
-    ArrayStorage* storage = thisObject->m_storage;
-
-    // Fast case - store to the vector.
-    if (i < thisObject->m_vectorLength) {
-        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
-        unsigned length = storage->m_length;
-
-        // Update m_length & m_numValuesInVector as necessary.
-        if (i >= length) {
-            length = i + 1;
-            storage->m_length = length;
-            ++storage->m_numValuesInVector;
-        } else if (!valueSlot)
-            ++storage->m_numValuesInVector;
-
-        valueSlot.set(exec->globalData(), thisObject, value);
-        thisObject->checkConsistency();
-        return;
-    }
-
-    // Handle 2^32-1 - this is not an array index (see ES5.1 15.4), and is treated as a regular property.
-    if (UNLIKELY(i > MAX_ARRAY_INDEX)) {
-        PutPropertySlot slot(shouldThrow);
-        thisObject->methodTable()->put(thisObject, exec, Identifier::from(exec, i), value, slot);
-        return;
-    }
-
-    // For all other cases, call putByIndexBeyondVectorLength.
-    thisObject->putByIndexBeyondVectorLength(exec, i, value, shouldThrow);
-    thisObject->checkConsistency();
-}
-
-void JSArray::putByIndexBeyondVectorLength(ExecState* exec, unsigned i, JSValue value, bool shouldThrow)
-{
-    JSGlobalData& globalData = exec->globalData();
-
-    // i should be a valid array index that is outside of the current vector.
-    ASSERT(i >= m_vectorLength);
-    ASSERT(i <= MAX_ARRAY_INDEX);
-
-    ArrayStorage* storage = m_storage;
-    SparseArrayValueMap* map = m_sparseValueMap;
-
-    // First, handle cases where we don't currently have a sparse map.
-    if (LIKELY(!map)) {
-        // If the array is not extensible, we should have entered dictionary mode, and created the spare map.
-        ASSERT(isExtensible());
-    
-        // Update m_length if necessary.
-        if (i >= storage->m_length)
-            storage->m_length = i + 1;
-
-        // Check that it is sensible to still be using a vector, and then try to grow the vector.
-        if (LIKELY((isDenseEnoughForVector(i, storage->m_numValuesInVector)) && increaseVectorLength(globalData, i + 1))) {
-            // success! - reread m_storage since it has likely been reallocated, and store to the vector.
-            storage = m_storage;
-            storage->m_vector[i].set(globalData, this, value);
-            ++storage->m_numValuesInVector;
-            return;
-        }
-        // We don't want to, or can't use a vector to hold this property - allocate a sparse map & add the value.
-        allocateSparseMap(exec->globalData());
-        map = m_sparseValueMap;
-        map->put(exec, this, i, value, shouldThrow);
-        return;
-    }
-
-    // Update m_length if necessary.
-    unsigned length = storage->m_length;
-    if (i >= length) {
-        // Prohibit growing the array if length is not writable.
-        if (map->lengthIsReadOnly() || !isExtensible()) {
-            if (shouldThrow)
-                throwTypeError(exec, ASCIILiteral(StrictModeReadonlyPropertyWriteError));
-            return;
-        }
-        length = i + 1;
-        storage->m_length = length;
-    }
-
-    // We are currently using a map - check whether we still want to be doing so.
-    // We will continue  to use a sparse map if SparseMode is set, a vector would be too sparse, or if allocation fails.
-    unsigned numValuesInArray = storage->m_numValuesInVector + map->size();
-    if (map->sparseMode() || !isDenseEnoughForVector(length, numValuesInArray) || !increaseVectorLength(exec->globalData(), length)) {
-        map->put(exec, this, i, value, shouldThrow);
-        return;
-    }
-
-    // Reread m_storage afterincreaseVectorLength, update m_numValuesInVector.
-    storage = m_storage;
-    storage->m_numValuesInVector = numValuesInArray;
-
-    // Copy all values from the map into the vector, and delete the map.
-    WriteBarrier<Unknown>* vector = storage->m_vector;
-    SparseArrayValueMap::const_iterator end = map->end();
-    for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
-        vector[it->first].set(globalData, this, it->second.getNonSparseMode());
-    deallocateSparseMap();
-
-    // Store the new property into the vector.
-    WriteBarrier<Unknown>& valueSlot = vector[i];
-    if (!valueSlot)
-        ++storage->m_numValuesInVector;
-    valueSlot.set(globalData, this, value);
-}
-
-bool JSArray::putDirectIndexBeyondVectorLength(ExecState* exec, unsigned i, JSValue value, PutDirectIndexMode mode)
-{
-    JSGlobalData& globalData = exec->globalData();
-
-    // i should be a valid array index that is outside of the current vector.
-    ASSERT(i >= m_vectorLength);
-    ASSERT(i <= MAX_ARRAY_INDEX);
-
-    ArrayStorage* storage = m_storage;
-    SparseArrayValueMap* map = m_sparseValueMap;
-
-    // First, handle cases where we don't currently have a sparse map.
-    if (LIKELY(!map)) {
-        // If the array is not extensible, we should have entered dictionary mode, and created the spare map.
-        ASSERT(isExtensible());
-    
-        // Update m_length if necessary.
-        if (i >= storage->m_length)
-            storage->m_length = i + 1;
-
-        // Check that it is sensible to still be using a vector, and then try to grow the vector.
-        if (LIKELY((isDenseEnoughForVector(i, storage->m_numValuesInVector)) && increaseVectorLength(globalData, i + 1))) {
-            // success! - reread m_storage since it has likely been reallocated, and store to the vector.
-            storage = m_storage;
-            storage->m_vector[i].set(globalData, this, value);
-            ++storage->m_numValuesInVector;
-            return true;
-        }
-        // We don't want to, or can't use a vector to hold this property - allocate a sparse map & add the value.
-        allocateSparseMap(exec->globalData());
-        map = m_sparseValueMap;
-        return map->putDirect(exec, this, i, value, mode);
-    }
-
-    // Update m_length if necessary.
-    unsigned length = storage->m_length;
-    if (i >= length) {
-        // Prohibit growing the array if length is not writable.
-        if (mode != PutDirectIndexLikePutDirect) {
-            if (map->lengthIsReadOnly())
-                return reject(exec, mode == PutDirectIndexShouldThrow, StrictModeReadonlyPropertyWriteError);
-            if (!isExtensible())
-                return reject(exec, mode == PutDirectIndexShouldThrow, "Attempting to define property on object that is not extensible.");
-        }
-        length = i + 1;
-        storage->m_length = length;
-    }
-
-    // We are currently using a map - check whether we still want to be doing so.
-    // We will continue  to use a sparse map if SparseMode is set, a vector would be too sparse, or if allocation fails.
-    unsigned numValuesInArray = storage->m_numValuesInVector + map->size();
-    if (map->sparseMode() || !isDenseEnoughForVector(length, numValuesInArray) || !increaseVectorLength(exec->globalData(), length))
-        return map->putDirect(exec, this, i, value, mode);
-
-    // Reread m_storage afterincreaseVectorLength, update m_numValuesInVector.
-    storage = m_storage;
-    storage->m_numValuesInVector = numValuesInArray;
-
-    // Copy all values from the map into the vector, and delete the map.
-    WriteBarrier<Unknown>* vector = storage->m_vector;
-    SparseArrayValueMap::const_iterator end = map->end();
-    for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
-        vector[it->first].set(globalData, this, it->second.getNonSparseMode());
-    deallocateSparseMap();
-
-    // Store the new property into the vector.
-    WriteBarrier<Unknown>& valueSlot = vector[i];
-    if (!valueSlot)
-        ++storage->m_numValuesInVector;
-    valueSlot.set(globalData, this, value);
-    return true;
-}
-
-bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, PropertyName propertyName)
-{
-    JSArray* thisObject = jsCast<JSArray*>(cell);
-    unsigned i = propertyName.asIndex();
-    if (i != PropertyName::NotAnIndex)
-        return thisObject->methodTable()->deletePropertyByIndex(thisObject, exec, i);
 
     if (propertyName == exec->propertyNames().length)
@@ -929 +232 @@
 
     return JSObject::deleteProperty(thisObject, exec, propertyName);
-}
-
-bool JSArray::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned i)
-{
-    JSArray* thisObject = jsCast<JSArray*>(cell);
-    thisObject->checkConsistency();
-
-    if (i > MAX_ARRAY_INDEX)
-        return thisObject->methodTable()->deleteProperty(thisObject, exec, Identifier::from(exec, i));
-
-    ArrayStorage* storage = thisObject->m_storage;
-    
-    if (i < thisObject->m_vectorLength) {
-        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
-        if (valueSlot) {
-            valueSlot.clear();
-            --storage->m_numValuesInVector;
-        }
-    } else if (SparseArrayValueMap* map = thisObject->m_sparseValueMap) {
-        SparseArrayValueMap::iterator it = map->find(i);
-        if (it != map->notFound()) {
-            if (it->second.attributes & DontDelete)
-                return false;
-            map->remove(it);
-        }
-    }
-
-    thisObject->checkConsistency();
-    return true;
 }
 
@@ -967 +241 @@
 }
 
-void JSArray::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
+void JSArray::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
 {
     JSArray* thisObject = jsCast<JSArray*>(object);
-    // FIXME: Filling PropertyNameArray with an identifier for every integer
-    // is incredibly inefficient for large arrays. We need a different approach,
-    // which almost certainly means a different structure for PropertyNameArray.
-
-    ArrayStorage* storage = thisObject->m_storage;
-    
-    unsigned usedVectorLength = min(storage->m_length, thisObject->m_vectorLength);
-    for (unsigned i = 0; i < usedVectorLength; ++i) {
-        if (storage->m_vector[i])
-            propertyNames.add(Identifier::from(exec, i));
-    }
-
-    if (SparseArrayValueMap* map = thisObject->m_sparseValueMap) {
-        Vector<unsigned> keys;
-        keys.reserveCapacity(map->size());
-        
-        SparseArrayValueMap::const_iterator end = map->end();
-        for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
-            if (mode == IncludeDontEnumProperties || !(it->second.attributes & DontEnum))
-                keys.append(static_cast<unsigned>(it->first));
-        }
-
-        qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort);
-        for (unsigned i = 0; i < keys.size(); ++i)
-            propertyNames.add(Identifier::from(exec, keys[i]));
-    }
 
     if (mode == IncludeDontEnumProperties)
         propertyNames.add(exec->propertyNames().length);
 
-    JSObject::getOwnPropertyNames(thisObject, exec, propertyNames, mode);
-}
-
-ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
-{
-    ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);
-
-    unsigned increasedLength;
-    unsigned maxInitLength = min(m_storage->m_length, 100000U);
-
-    if (desiredLength < maxInitLength)
-        increasedLength = maxInitLength;
-    else if (!m_vectorLength)
-        increasedLength = max(desiredLength, lastArraySize);
-    else {
-        // Mathematically equivalent to:
-        //   increasedLength = (newLength * 3 + 1) / 2;
-        // or:
-        //   increasedLength = (unsigned)ceil(newLength * 1.5));
-        // This form is not prone to internal overflow.
-        increasedLength = desiredLength + (desiredLength >> 1) + (desiredLength & 1);
-    }
-
-    ASSERT(increasedLength >= desiredLength);
-
-    lastArraySize = min(increasedLength, FIRST_VECTOR_GROW);
-
-    return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
-}
-
-bool JSArray::increaseVectorLength(JSGlobalData& globalData, unsigned newLength)
-{
-    // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
-    // to the vector. Callers have to account for that, because they can do it more efficiently.
-    if (newLength > MAX_STORAGE_VECTOR_LENGTH)
-        return false;
-
-    ArrayStorage* storage = m_storage;
-
-    unsigned vectorLength = m_vectorLength;
-    ASSERT(newLength > vectorLength);
-    unsigned newVectorLength = getNewVectorLength(newLength);
-
-    // Fast case - there is no precapacity. In these cases a realloc makes sense.
-    if (LIKELY(!m_indexBias)) {
-        void* newStorage = storage->m_allocBase;
-        if (!globalData.heap.tryReallocateStorage(&newStorage, storageSize(vectorLength), storageSize(newVectorLength)))
-            return false;
-
-        storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(newStorage));
-        m_storage->m_allocBase = newStorage;
-        ASSERT(m_storage->m_allocBase);
-
-        m_vectorLength = newVectorLength;
-        
-        return true;
-    }
-
-    // Remove some, but not all of the precapacity. Atomic decay, & capped to not overflow array length.
-    unsigned newIndexBias = min(m_indexBias >> 1, MAX_STORAGE_VECTOR_LENGTH - newVectorLength);
-    // Calculate new stoarge capcity, allowing room for the pre-capacity.
-    unsigned newStorageCapacity = newVectorLength + newIndexBias;
-    void* newAllocBase = 0;
-    if (!globalData.heap.tryAllocateStorage(storageSize(newStorageCapacity), &newAllocBase))    
-        return false;
-    // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH.
-    ASSERT(m_vectorLength <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - m_vectorLength) >= m_indexBias);
-
-    m_vectorLength = newVectorLength;
-    m_indexBias = newIndexBias;
-    m_storage = reinterpret_cast_ptr<ArrayStorage*>(reinterpret_cast<WriteBarrier<Unknown>*>(newAllocBase) + m_indexBias);
-
-    // Copy the ArrayStorage header & current contents of the vector.
-    memmove(m_storage, storage, storageSize(vectorLength));
-
-    // Free the old allocation, update m_allocBase.
-    m_storage->m_allocBase = newAllocBase;
-
-    return true;
+    JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode);
 }
 
@@ -1084 +254 @@
 bool JSArray::unshiftCountSlowCase(JSGlobalData& globalData, unsigned count)
 {
+    ArrayStorage* storage = ensureArrayStorage(globalData);
+    Butterfly* butterfly = storage->butterfly();
+    unsigned propertyCapacity = structure()->outOfLineCapacity();
+    unsigned propertySize = structure()->outOfLineSize();
+
     // If not, we should have handled this on the fast path.
-    ASSERT(count > m_indexBias);
-
-    ArrayStorage* storage = m_storage;
+    ASSERT(count > storage->m_indexBias);
 
     // Step 1:
@@ -1096 +269 @@
     //  * desiredCapacity - how large should we like to grow the vector to - based on 2x requiredVectorLength.
 
-    unsigned length = storage->m_length;
-    unsigned usedVectorLength = min(m_vectorLength, length);
+    unsigned length = storage->length();
+    unsigned usedVectorLength = min(storage->vectorLength(), length);
     ASSERT(usedVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
     // Check that required vector length is possible, in an overflow-safe fashion.
@@ -1105 +278 @@
     ASSERT(requiredVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
     // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH.
-    ASSERT(m_vectorLength <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - m_vectorLength) >= m_indexBias);
-    unsigned currentCapacity = m_vectorLength + m_indexBias;
+    ASSERT(storage->vectorLength() <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - storage->vectorLength()) >= storage->m_indexBias);
+    unsigned currentCapacity = storage->vectorLength() + storage->m_indexBias;
     // The calculation of desiredCapacity won't overflow, due to the range of MAX_STORAGE_VECTOR_LENGTH.
     unsigned desiredCapacity = min(MAX_STORAGE_VECTOR_LENGTH, max(BASE_VECTOR_LEN, requiredVectorLength) << 1);
@@ -1117 +290 @@
     // If the current storage array is sufficiently large (but not too large!) then just keep using it.
     if (currentCapacity > desiredCapacity && isDenseEnoughForVector(currentCapacity, requiredVectorLength)) {
-        newAllocBase = storage->m_allocBase;
+        newAllocBase = butterfly->base(structure());
         newStorageCapacity = currentCapacity;
     } else {
-        if (!globalData.heap.tryAllocateStorage(storageSize(desiredCapacity), &newAllocBase))
+        size_t newSize = Butterfly::totalSize(0, propertyCapacity, true, ArrayStorage::sizeFor(desiredCapacity));
+        if (!globalData.heap.tryAllocateStorage(newSize, &newAllocBase))
             return false;
         newStorageCapacity = desiredCapacity;
@@ -1133 +307 @@
     // vector with half the post-capacity it had previously.
     unsigned postCapacity = 0;
-    if (length < m_vectorLength) {
+    if (length < storage->vectorLength()) {
         // Atomic decay, + the post-capacity cannot be greater than what is available.
-        postCapacity = min((m_vectorLength - length) >> 1, newStorageCapacity - requiredVectorLength);
+        postCapacity = min((storage->vectorLength() - length) >> 1, newStorageCapacity - requiredVectorLength);
         // If we're moving contents within the same allocation, the post-capacity is being reduced.
-        ASSERT(newAllocBase != storage->m_allocBase || postCapacity < m_vectorLength - length);
-    }
-
-    m_vectorLength = requiredVectorLength + postCapacity;
-    m_indexBias = newStorageCapacity - m_vectorLength;
-    m_storage = reinterpret_cast_ptr<ArrayStorage*>(reinterpret_cast<WriteBarrier<Unknown>*>(newAllocBase) + m_indexBias);
-
-    // Step 4:
-    // Copy array data / header into their new locations, clear post-capacity & free any old allocation.
-
-    // If this is being moved within the existing buffer of memory, we are always shifting data
-    // to the right (since count > m_indexBias). As such this memmove cannot trample the header.
-    memmove(m_storage->m_vector + count, storage->m_vector, sizeof(WriteBarrier<Unknown>) * usedVectorLength);
-    memmove(m_storage, storage, storageSize(0));
-
-    // Are we copying into a new allocation?
-    if (newAllocBase != m_storage->m_allocBase) {
-        // Free the old allocation, update m_allocBase.
-        m_storage->m_allocBase = newAllocBase;
-    }
+        ASSERT(newAllocBase != butterfly->base(structure()) || postCapacity < storage->vectorLength() - length);
+    }
+    
+    unsigned newVectorLength = requiredVectorLength + postCapacity;
+    unsigned newIndexBias = newStorageCapacity - newVectorLength;
+
+    Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, newIndexBias, propertyCapacity);
+    
+    memmove(newButterfly->arrayStorage()->m_vector + count, storage->m_vector, sizeof(JSValue) * usedVectorLength);
+    memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
+    
+    newButterfly->arrayStorage()->setVectorLength(newVectorLength);
+    newButterfly->arrayStorage()->m_indexBias = newIndexBias;
+    
+    m_butterfly = newButterfly;
 
     return true;
@@ -1163 +332 @@
 bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)
 {
-    checkConsistency();
-
-    ArrayStorage* storage = m_storage;
-    unsigned length = storage->m_length;
+    checkIndexingConsistency();
+
+    ArrayStorage* storage = ensureArrayStorage(exec->globalData());
+    unsigned length = storage->length();
 
     // If the length is read only then we enter sparse mode, so should enter the following 'if'.
-    ASSERT(isLengthWritable() || m_sparseValueMap);
-
-    if (SparseArrayValueMap* map = m_sparseValueMap) {
+    ASSERT(isLengthWritable() || storage->m_sparseMap);
+
+    if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
         // Fail if the length is not writable.
         if (map->lengthIsReadOnly())
@@ -1198 +367 @@
                     ASSERT(it != map->notFound());
                     if (it->second.attributes & DontDelete) {
-                        storage->m_length = index + 1;
+                        storage->setLength(index + 1);
                         return reject(exec, throwException, "Unable to delete property.");
                     }
@@ -1207 +376 @@
                     map->remove(keys[i]);
                 if (map->isEmpty())
-                    deallocateSparseMap();
+                    deallocateSparseIndexMap();
             }
         }
@@ -1214 +383 @@
     if (newLength < length) {
         // Delete properties from the vector.
-        unsigned usedVectorLength = min(length, m_vectorLength);
+        unsigned usedVectorLength = min(length, storage->vectorLength());
         for (unsigned i = newLength; i < usedVectorLength; ++i) {
             WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
@@ -1223 +392 @@
     }
 
-    storage->m_length = newLength;
-
-    checkConsistency();
+    storage->setLength(newLength);
+
+    checkIndexingConsistency();
     return true;
 }
@@ -1231 +400 @@
 JSValue JSArray::pop(ExecState* exec)
 {
-    checkConsistency();
-    ArrayStorage* storage = m_storage;
-    
-    unsigned length = storage->m_length;
-    if (!length) {
-        if (!isLengthWritable())
-            throwTypeError(exec, ASCIILiteral(StrictModeReadonlyPropertyWriteError));
+    checkIndexingConsistency();
+    
+    switch (structure()->indexingType()) {
+    case Array:
         return jsUndefined();
-    }
-
-    unsigned index = length - 1;
-    if (index < m_vectorLength) {
-        WriteBarrier<Unknown>& valueSlot = storage->m_vector[index];
-        if (valueSlot) {
-            --storage->m_numValuesInVector;
-            JSValue element = valueSlot.get();
-            valueSlot.clear();
+        
+    case ArrayWithArrayStorage: {
+        ArrayStorage* storage = m_butterfly->arrayStorage();
+    
+        unsigned length = storage->length();
+        if (!length) {
+            if (!isLengthWritable())
+                throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
+            return jsUndefined();
+        }
+
+        unsigned index = length - 1;
+        if (index < storage->vectorLength()) {
+            WriteBarrier<Unknown>& valueSlot = storage->m_vector[index];
+            if (valueSlot) {
+                --storage->m_numValuesInVector;
+                JSValue element = valueSlot.get();
+                valueSlot.clear();
             
-            ASSERT(isLengthWritable());
-            storage->m_length = index;
-            checkConsistency();
-            return element;
-        }
-    }
-
-    // Let element be the result of calling the [[Get]] internal method of O with argument indx.
-    JSValue element = get(exec, index);
-    if (exec->hadException())
-        return jsUndefined();
-    // Call the [[Delete]] internal method of O with arguments indx and true.
-    if (!deletePropertyByIndex(this, exec, index)) {
-        throwTypeError(exec, ASCIILiteral("Unable to delete property."));
-        return jsUndefined();
-    }
-    // Call the [[Put]] internal method of O with arguments "length", indx, and true.
-    setLength(exec, index, true);
-    // Return element.
-    checkConsistency();
-    return element;
+                ASSERT(isLengthWritable());
+                storage->setLength(index);
+                checkIndexingConsistency();
+                return element;
+            }
+        }
+
+        // Let element be the result of calling the [[Get]] internal method of O with argument indx.
+        JSValue element = get(exec, index);
+        if (exec->hadException())
+            return jsUndefined();
+        // Call the [[Delete]] internal method of O with arguments indx and true.
+        if (!deletePropertyByIndex(this, exec, index)) {
+            throwTypeError(exec, "Unable to delete property.");
+            return jsUndefined();
+        }
+        // Call the [[Put]] internal method of O with arguments "length", indx, and true.
+        setLength(exec, index, true);
+        // Return element.
+        checkIndexingConsistency();
+        return element;
+    }
+        
+    default:
+        ASSERT_NOT_REACHED();
+        return JSValue();
+    }
 }
 
@@ -1277 +458 @@
 void JSArray::push(ExecState* exec, JSValue value)
 {
-    checkConsistency();
-    ArrayStorage* storage = m_storage;
-
-    // Fast case - push within vector, always update m_length & m_numValuesInVector.
-    unsigned length = storage->m_length;
-    if (length < m_vectorLength) {
-        storage->m_vector[length].set(exec->globalData(), this, value);
-        storage->m_length = length + 1;
-        ++storage->m_numValuesInVector;
-        checkConsistency();
-        return;
-    }
-
-    // Pushing to an array of length 2^32-1 stores the property, but throws a range error.
-    if (UNLIKELY(storage->m_length == 0xFFFFFFFFu)) {
-        methodTable()->putByIndex(this, exec, storage->m_length, value, true);
-        // Per ES5.1 15.4.4.7 step 6 & 15.4.5.1 step 3.d.
-        if (!exec->hadException())
-            throwError(exec, createRangeError(exec, ASCIILiteral("Invalid array length")));
-        return;
-    }
-
-    // Handled the same as putIndex.
-    putByIndexBeyondVectorLength(exec, storage->m_length, value, true);
-    checkConsistency();
-}
-
-bool JSArray::shiftCount(ExecState*, unsigned count)
+    checkIndexingConsistency();
+    
+    switch (structure()->indexingType()) {
+    case Array: {
+        putByIndexBeyondVectorLengthWithArrayStorage(exec, 0, value, true, createInitialArrayStorage(exec->globalData()));
+        break;
+    }
+        
+    case ArrayWithArrayStorage: {
+        ArrayStorage* storage = m_butterfly->arrayStorage();
+
+        // Fast case - push within vector, always update m_length & m_numValuesInVector.
+        unsigned length = storage->length();
+        if (length < storage->vectorLength()) {
+            storage->m_vector[length].set(exec->globalData(), this, value);
+            storage->setLength(length + 1);
+            ++storage->m_numValuesInVector;
+            checkIndexingConsistency();
+            return;
+        }
+
+        // Pushing to an array of length 2^32-1 stores the property, but throws a range error.
+        if (UNLIKELY(storage->length() == 0xFFFFFFFFu)) {
+            methodTable()->putByIndex(this, exec, storage->length(), value, true);
+            // Per ES5.1 15.4.4.7 step 6 & 15.4.5.1 step 3.d.
+            if (!exec->hadException())
+                throwError(exec, createRangeError(exec, "Invalid array length"));
+            return;
+        }
+
+        // Handled the same as putIndex.
+        putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage);
+        checkIndexingConsistency();
+        break;
+    }
+        
+    default:
+        ASSERT_NOT_REACHED();
+    }
+}
+
+bool JSArray::shiftCount(ExecState* exec, unsigned count)
 {
     ASSERT(count > 0);
     
-    ArrayStorage* storage = m_storage;
-    
-    unsigned oldLength = storage->m_length;
+    ArrayStorage* storage = ensureArrayStorage(exec->globalData());
+    
+    unsigned oldLength = storage->length();
     
     // If the array contains holes or is otherwise in an abnormal state,
     // use the generic algorithm in ArrayPrototype.
-    if (oldLength != storage->m_numValuesInVector || inSparseMode())
+    if (oldLength != storage->m_numValuesInVector || inSparseIndexingMode())
         return false;
 
@@ -1321 +516 @@
     
     storage->m_numValuesInVector -= count;
-    storage->m_length -= count;
-    
-    if (m_vectorLength) {
-        count = min(m_vectorLength, (unsigned)count);
-        
-        m_vectorLength -= count;
-        
-        if (m_vectorLength) {
-            char* newBaseStorage = reinterpret_cast<char*>(storage) + count * sizeof(WriteBarrier<Unknown>);
-            memmove(newBaseStorage, storage, storageSize(0));
-            m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
-
-            m_indexBias += count;
+    storage->setLength(oldLength - count);
+    
+    unsigned vectorLength = storage->vectorLength();
+    if (vectorLength) {
+        count = min(vectorLength, (unsigned)count);
+        
+        vectorLength -= count;
+        storage->setVectorLength(vectorLength);
+        
+        if (vectorLength) {
+            m_butterfly = m_butterfly->shift(structure(), count);
+            storage = m_butterfly->arrayStorage();
+            storage->m_indexBias += count;
         }
     }
@@ -1342 +537 @@
 bool JSArray::unshiftCount(ExecState* exec, unsigned count)
 {
-    ArrayStorage* storage = m_storage;
-    unsigned length = storage->m_length;
+    ArrayStorage* storage = ensureArrayStorage(exec->globalData());
+    unsigned length = storage->length();
 
     // If the array contains holes or is otherwise in an abnormal state,
     // use the generic algorithm in ArrayPrototype.
-    if (length != storage->m_numValuesInVector || inSparseMode())
+    if (length != storage->m_numValuesInVector || storage->inSparseMode())
         return false;
 
-    if (m_indexBias >= count) {
-        m_indexBias -= count;
-        char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(WriteBarrier<Unknown>);
-        memmove(newBaseStorage, storage, storageSize(0));
-        m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
-        m_vectorLength += count;
+    if (storage->m_indexBias >= count) {
+        m_butterfly = storage->butterfly()->unshift(structure(), count);
+        storage = m_butterfly->arrayStorage();
+        storage->m_indexBias -= count;
+        storage->setVectorLength(storage->vectorLength() + count);
     } else if (!unshiftCountSlowCase(exec->globalData(), count)) {
         throwOutOfMemoryError(exec);
@@ -1361 +555 @@
     }
 
-    WriteBarrier<Unknown>* vector = m_storage->m_vector;
+    WriteBarrier<Unknown>* vector = storage->m_vector;
     for (unsigned i = 0; i < count; i++)
         vector[i].clear();
@@ -1367 +561 @@
 }
 
-void JSArray::visitChildren(JSCell* cell, SlotVisitor& visitor)
-{
-    JSArray* thisObject = jsCast<JSArray*>(cell);
-    ASSERT_GC_OBJECT_INHERITS(thisObject, &s_info);
-    COMPILE_ASSERT(StructureFlags & OverridesVisitChildren, OverridesVisitChildrenWithoutSettingFlag);
-    ASSERT(thisObject->structure()->typeInfo().overridesVisitChildren());
-
-    JSNonFinalObject::visitChildren(thisObject, visitor);
-
-    if (thisObject->m_storage) {
-        MARK_LOG_MESSAGE1("[%u]: ", thisObject->length());
-
-        ArrayStorage* storage = thisObject->m_storage;
-        void* baseStorage = storage->m_allocBase;
-
-        visitor.copyAndAppend(reinterpret_cast<void**>(&baseStorage), storageSize(thisObject->m_vectorLength + thisObject->m_indexBias), storage->m_vector->slot(), thisObject->m_vectorLength);
-
-        if (baseStorage != thisObject->m_storage->m_allocBase) {
-            thisObject->m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + sizeof(JSValue) * thisObject->m_indexBias);
-            thisObject->m_storage->m_allocBase = baseStorage;
-            ASSERT(thisObject->m_storage->m_allocBase);
-        }
-    }
-
-    if (SparseArrayValueMap* map = thisObject->m_sparseValueMap)
-        map->visitChildren(visitor);
-}
-
 static int compareNumbersForQSort(const void* a, const void* b)
 {
@@ -1411 +577 @@
 void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
 {
-    ASSERT(!inSparseMode());
-
-    ArrayStorage* storage = m_storage;
-
-    unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
-    if (m_sparseValueMap) {
-        throwOutOfMemoryError(exec);
-        return;
-    }
-
-    if (!lengthNotIncludingUndefined)
-        return;
-        
-    bool allValuesAreNumbers = true;
-    size_t size = storage->m_numValuesInVector;
-    for (size_t i = 0; i < size; ++i) {
-        if (!storage->m_vector[i].isNumber()) {
-            allValuesAreNumbers = false;
-            break;
-        }
-    }
-
-    if (!allValuesAreNumbers)
-        return sort(exec, compareFunction, callType, callData);
-
-    // For numeric comparison, which is fast, qsort is faster than mergesort. We
-    // also don't require mergesort's stability, since there's no user visible
-    // side-effect from swapping the order of equal primitive values.
-    qsort(storage->m_vector, size, sizeof(WriteBarrier<Unknown>), compareNumbersForQSort);
-
-    checkConsistency(SortConsistencyCheck);
+    ASSERT(!inSparseIndexingMode());
+
+    switch (structure()->indexingType()) {
+    case Array:
+        return;
+        
+    case ArrayWithArrayStorage: {
+        unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
+        ArrayStorage* storage = m_butterfly->arrayStorage();
+        
+        if (storage->m_sparseMap.get()) {
+            throwOutOfMemoryError(exec);
+            return;
+        }
+        
+        if (!lengthNotIncludingUndefined)
+            return;
+        
+        bool allValuesAreNumbers = true;
+        size_t size = storage->m_numValuesInVector;
+        for (size_t i = 0; i < size; ++i) {
+            if (!storage->m_vector[i].isNumber()) {
+                allValuesAreNumbers = false;
+                break;
+            }
+        }
+        
+        if (!allValuesAreNumbers)
+            return sort(exec, compareFunction, callType, callData);
+        
+        // For numeric comparison, which is fast, qsort is faster than mergesort. We
+        // also don't require mergesort's stability, since there's no user visible
+        // side-effect from swapping the order of equal primitive values.
+        qsort(storage->m_vector, size, sizeof(WriteBarrier<Unknown>), compareNumbersForQSort);
+        
+        checkIndexingConsistency(SortConsistencyCheck);
+        return;
+    }
+        
+    default:
+        ASSERT_NOT_REACHED();
+    }
 }
 
 void JSArray::sort(ExecState* exec)
 {
-    ASSERT(!inSparseMode());
-
-    unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
-    if (m_sparseValueMap) {
-        throwOutOfMemoryError(exec);
-        return;
-    }
-
-    if (!lengthNotIncludingUndefined)
-        return;
-
-    // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
-    // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
-    // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
-    // random or otherwise changing results, effectively making compare function inconsistent.
-
-    Vector<ValueStringPair> values(lengthNotIncludingUndefined);
-    if (!values.begin()) {
-        throwOutOfMemoryError(exec);
-        return;
-    }
-    
-    Heap::heap(this)->pushTempSortVector(&values);
-
-    bool isSortingPrimitiveValues = true;
-    for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
-        JSValue value = m_storage->m_vector[i].get();
-        ASSERT(!value.isUndefined());
-        values[i].first = value;
-        isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive();
-    }
-
-    // FIXME: The following loop continues to call toString on subsequent values even after
-    // a toString call raises an exception.
-
-    for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
-        values[i].second = values[i].first.toWTFStringInline(exec);
-
-    if (exec->hadException()) {
+    ASSERT(!inSparseIndexingMode());
+    
+    switch (structure()->indexingType()) {
+    case Array:
+        return;
+        
+    case ArrayWithArrayStorage: {
+        unsigned lengthNotIncludingUndefined = compactForSorting(exec->globalData());
+        ArrayStorage* storage = m_butterfly->arrayStorage();
+        if (storage->m_sparseMap.get()) {
+            throwOutOfMemoryError(exec);
+            return;
+        }
+        
+        if (!lengthNotIncludingUndefined)
+            return;
+        
+        // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
+        // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
+        // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
+        // random or otherwise changing results, effectively making compare function inconsistent.
+        
+        Vector<ValueStringPair> values(lengthNotIncludingUndefined);
+        if (!values.begin()) {
+            throwOutOfMemoryError(exec);
+            return;
+        }
+        
+        Heap::heap(this)->pushTempSortVector(&values);
+        
+        bool isSortingPrimitiveValues = true;
+        for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
+            JSValue value = storage->m_vector[i].get();
+            ASSERT(!value.isUndefined());
+            values[i].first = value;
+            isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive();
+        }
+        
+        // FIXME: The following loop continues to call toString on subsequent values even after
+        // a toString call raises an exception.
+        
+        for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
+            values[i].second = values[i].first.toWTFStringInline(exec);
+        
+        if (exec->hadException()) {
+            Heap::heap(this)->popTempSortVector(&values);
+            return;
+        }
+        
+        // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
+        // than O(N log N).
+        
+#if HAVE(MERGESORT)
+        if (isSortingPrimitiveValues)
+            qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+        else
+            mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+#else
+        // FIXME: The qsort library function is likely to not be a stable sort.
+        // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
+        qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+#endif
+        
+        // If the toString function changed the length of the array or vector storage,
+        // increase the length to handle the orignal number of actual values.
+        if (storage->vectorLength() < lengthNotIncludingUndefined) {
+            increaseVectorLength(exec->globalData(), lengthNotIncludingUndefined);
+            storage = m_butterfly->arrayStorage();
+        }
+        if (storage->length() < lengthNotIncludingUndefined)
+            storage->setLength(lengthNotIncludingUndefined);
+        
+        JSGlobalData& globalData = exec->globalData();
+        for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
+            storage->m_vector[i].set(globalData, this, values[i].first);
+        
         Heap::heap(this)->popTempSortVector(&values);
-        return;
-    }
-
-    // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
-    // than O(N log N).
-
-#if HAVE(MERGESORT)
-    if (isSortingPrimitiveValues)
-        qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
-    else
-        mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
-#else
-    // FIXME: The qsort library function is likely to not be a stable sort.
-    // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
-    qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
-#endif
-
-    // If the toString function changed the length of the array or vector storage,
-    // increase the length to handle the orignal number of actual values.
-    if (m_vectorLength < lengthNotIncludingUndefined)
-        increaseVectorLength(exec->globalData(), lengthNotIncludingUndefined);
-    if (m_storage->m_length < lengthNotIncludingUndefined)
-        m_storage->m_length = lengthNotIncludingUndefined;
-
-    JSGlobalData& globalData = exec->globalData();
-    for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
-        m_storage->m_vector[i].set(globalData, this, values[i].first);
-
-    Heap::heap(this)->popTempSortVector(&values);
-    
-    checkConsistency(SortConsistencyCheck);
+        
+        checkIndexingConsistency(SortConsistencyCheck);
+        return;
+    }
+        
+    default:
+        ASSERT_NOT_REACHED();
+    }
 }
 
@@ -1598 +789 @@
 void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
 {
-    ASSERT(!inSparseMode());
-
-    checkConsistency();
-
-    // FIXME: This ignores exceptions raised in the compare function or in toNumber.
-
-    // The maximum tree depth is compiled in - but the caller is clearly up to no good
-    // if a larger array is passed.
-    ASSERT(m_storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
-    if (m_storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
-        return;
-
-    unsigned usedVectorLength = min(m_storage->m_length, m_vectorLength);
-    unsigned nodeCount = usedVectorLength + (m_sparseValueMap ? m_sparseValueMap->size() : 0);
-
-    if (!nodeCount)
-        return;
-
-    AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
-    tree.abstractor().m_exec = exec;
-    tree.abstractor().m_compareFunction = compareFunction;
-    tree.abstractor().m_compareCallType = callType;
-    tree.abstractor().m_compareCallData = &callData;
-    tree.abstractor().m_nodes.grow(nodeCount);
-
-    if (callType == CallTypeJS)
-        tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, jsCast<JSFunction*>(compareFunction), 2));
-
-    if (!tree.abstractor().m_nodes.begin()) {
-        throwOutOfMemoryError(exec);
-        return;
-    }
-
-    // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
-    // right out from under us while we're building the tree here.
-
-    unsigned numDefined = 0;
-    unsigned numUndefined = 0;
-
-    // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
-    for (; numDefined < usedVectorLength; ++numDefined) {
-        JSValue v = m_storage->m_vector[numDefined].get();
-        if (!v || v.isUndefined())
-            break;
-        tree.abstractor().m_nodes[numDefined].value = v;
-        tree.insert(numDefined);
-    }
-    for (unsigned i = numDefined; i < usedVectorLength; ++i) {
-        JSValue v = m_storage->m_vector[i].get();
-        if (v) {
-            if (v.isUndefined())
-                ++numUndefined;
-            else {
-                tree.abstractor().m_nodes[numDefined].value = v;
+    ASSERT(!inSparseIndexingMode());
+    
+    switch (structure()->indexingType()) {
+    case Array:
+        return;
+        
+    case ArrayWithArrayStorage: {
+        ArrayStorage* storage = m_butterfly->arrayStorage();
+        checkIndexingConsistency();
+        
+        // FIXME: This ignores exceptions raised in the compare function or in toNumber.
+        
+        // The maximum tree depth is compiled in - but the caller is clearly up to no good
+        // if a larger array is passed.
+        ASSERT(storage->length() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
+        if (storage->length() > static_cast<unsigned>(std::numeric_limits<int>::max()))
+            return;
+        
+        unsigned usedVectorLength = min(storage->length(), storage->vectorLength());
+        unsigned nodeCount = usedVectorLength + (storage->m_sparseMap ? storage->m_sparseMap->size() : 0);
+        
+        if (!nodeCount)
+            return;
+        
+        AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
+        tree.abstractor().m_exec = exec;
+        tree.abstractor().m_compareFunction = compareFunction;
+        tree.abstractor().m_compareCallType = callType;
+        tree.abstractor().m_compareCallData = &callData;
+        tree.abstractor().m_nodes.grow(nodeCount);
+        
+        if (callType == CallTypeJS)
+            tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, jsCast<JSFunction*>(compareFunction), 2));
+        
+        if (!tree.abstractor().m_nodes.begin()) {
+            throwOutOfMemoryError(exec);
+            return;
+        }
+        
+        // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
+        // right out from under us while we're building the tree here.
+        
+        unsigned numDefined = 0;
+        unsigned numUndefined = 0;
+        
+        // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
+        for (; numDefined < usedVectorLength; ++numDefined) {
+            JSValue v = storage->m_vector[numDefined].get();
+            if (!v || v.isUndefined())
+                break;
+            tree.abstractor().m_nodes[numDefined].value = v;
+            tree.insert(numDefined);
+        }
+        for (unsigned i = numDefined; i < usedVectorLength; ++i) {
+            JSValue v = storage->m_vector[i].get();
+            if (v) {
+                if (v.isUndefined())
+                    ++numUndefined;
+                else {
+                    tree.abstractor().m_nodes[numDefined].value = v;
+                    tree.insert(numDefined);
+                    ++numDefined;
+                }
+            }
+        }
+        
+        unsigned newUsedVectorLength = numDefined + numUndefined;
+        
+        if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
+            newUsedVectorLength += map->size();
+            if (newUsedVectorLength > storage->vectorLength()) {
+                // Check that it is possible to allocate an array large enough to hold all the entries.
+                if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(exec->globalData(), newUsedVectorLength)) {
+                    throwOutOfMemoryError(exec);
+                    return;
+                }
+                storage = m_butterfly->arrayStorage();
+            }
+            
+            SparseArrayValueMap::const_iterator end = map->end();
+            for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
+                tree.abstractor().m_nodes[numDefined].value = it->second.getNonSparseMode();
                 tree.insert(numDefined);
                 ++numDefined;
             }
-        }
-    }
-
-    unsigned newUsedVectorLength = numDefined + numUndefined;
-
-    if (SparseArrayValueMap* map = m_sparseValueMap) {
-        newUsedVectorLength += map->size();
-        if (newUsedVectorLength > m_vectorLength) {
-            // Check that it is possible to allocate an array large enough to hold all the entries.
-            if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(exec->globalData(), newUsedVectorLength)) {
-                throwOutOfMemoryError(exec);
-                return;
+            
+            deallocateSparseIndexMap();
+        }
+        
+        ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
+        
+        // FIXME: If the compare function changed the length of the array, the following might be
+        // modifying the vector incorrectly.
+        
+        // Copy the values back into m_storage.
+        AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
+        iter.start_iter_least(tree);
+        JSGlobalData& globalData = exec->globalData();
+        for (unsigned i = 0; i < numDefined; ++i) {
+            storage->m_vector[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value);
+            ++iter;
+        }
+        
+        // Put undefined values back in.
+        for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
+            storage->m_vector[i].setUndefined();
+        
+        // Ensure that unused values in the vector are zeroed out.
+        for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
+            storage->m_vector[i].clear();
+        
+        storage->m_numValuesInVector = newUsedVectorLength;
+        
+        checkIndexingConsistency(SortConsistencyCheck);
+        return;
+    }
+        
+    default:
+        ASSERT_NOT_REACHED();
+    }
+}
+
+void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
+{
+    switch (structure()->indexingType()) {
+    case Array:
+        return;
+    
+    case ArrayWithArrayStorage: {
+        ArrayStorage* storage = m_butterfly->arrayStorage();
+        
+        WriteBarrier<Unknown>* vector = storage->m_vector;
+        unsigned vectorEnd = min(storage->length(), storage->vectorLength());
+        unsigned i = 0;
+        for (; i < vectorEnd; ++i) {
+            WriteBarrier<Unknown>& v = vector[i];
+            if (!v)
+                break;
+            args.append(v.get());
+        }
+        
+        for (; i < storage->length(); ++i)
+            args.append(get(exec, i));
+        return;
+    }
+        
+    default:
+        ASSERT_NOT_REACHED();
+    }
+}
+
+void JSArray::copyToArguments(ExecState* exec, CallFrame* callFrame, uint32_t length)
+{
+    ASSERT(length == this->length());
+    switch (structure()->indexingType()) {
+    case Array:
+        return;
+        
+    case ArrayWithArrayStorage: {
+        ArrayStorage* storage = m_butterfly->arrayStorage();
+        unsigned i = 0;
+        WriteBarrier<Unknown>* vector = storage->m_vector;
+        unsigned vectorEnd = min(length, storage->vectorLength());
+        for (; i < vectorEnd; ++i) {
+            WriteBarrier<Unknown>& v = vector[i];
+            if (!v)
+                break;
+            callFrame->setArgument(i, v.get());
+        }
+        
+        for (; i < length; ++i)
+            callFrame->setArgument(i, get(exec, i));
+        return;
+    }
+        
+    default:
+        ASSERT_NOT_REACHED();
+    }
+}
+
+unsigned JSArray::compactForSorting(JSGlobalData& globalData)
+{
+    ASSERT(!inSparseIndexingMode());
+
+    checkIndexingConsistency();
+    
+    switch (structure()->indexingType()) {
+    case Array:
+        return 0;
+
+    case ArrayWithArrayStorage: {
+        ArrayStorage* storage = m_butterfly->arrayStorage();
+        
+        unsigned usedVectorLength = min(storage->length(), storage->vectorLength());
+        
+        unsigned numDefined = 0;
+        unsigned numUndefined = 0;
+        
+        for (; numDefined < usedVectorLength; ++numDefined) {
+            JSValue v = storage->m_vector[numDefined].get();
+            if (!v || v.isUndefined())
+                break;
+        }
+        
+        for (unsigned i = numDefined; i < usedVectorLength; ++i) {
+            JSValue v = storage->m_vector[i].get();
+            if (v) {
+                if (v.isUndefined())
+                    ++numUndefined;
+                else
+                    storage->m_vector[numDefined++].setWithoutWriteBarrier(v);
             }
         }
-
-        SparseArrayValueMap::const_iterator end = map->end();
-        for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
-            tree.abstractor().m_nodes[numDefined].value = it->second.getNonSparseMode();
-            tree.insert(numDefined);
-            ++numDefined;
-        }
-
-        deallocateSparseMap();
-    }
-
-    ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
-
-    // FIXME: If the compare function changed the length of the array, the following might be
-    // modifying the vector incorrectly.
-
-    // Copy the values back into m_storage.
-    AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
-    iter.start_iter_least(tree);
-    JSGlobalData& globalData = exec->globalData();
-    for (unsigned i = 0; i < numDefined; ++i) {
-        m_storage->m_vector[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value);
-        ++iter;
-    }
-
-    // Put undefined values back in.
-    for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
-        m_storage->m_vector[i].setUndefined();
-
-    // Ensure that unused values in the vector are zeroed out.
-    for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
-        m_storage->m_vector[i].clear();
-
-    m_storage->m_numValuesInVector = newUsedVectorLength;
-
-    checkConsistency(SortConsistencyCheck);
-}
-
-void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
-{
-    ArrayStorage* storage = m_storage;
-
-    WriteBarrier<Unknown>* vector = storage->m_vector;
-    unsigned vectorEnd = min(storage->m_length, m_vectorLength);
-    unsigned i = 0;
-    for (; i < vectorEnd; ++i) {
-        WriteBarrier<Unknown>& v = vector[i];
-        if (!v)
-            break;
-        args.append(v.get());
-    }
-
-    for (; i < storage->m_length; ++i)
-        args.append(get(exec, i));
-}
-
-void JSArray::copyToArguments(ExecState* exec, CallFrame* callFrame, uint32_t length)
-{
-    ASSERT(length == this->length());
-    UNUSED_PARAM(length);
-    unsigned i = 0;
-    WriteBarrier<Unknown>* vector = m_storage->m_vector;
-    unsigned vectorEnd = min(length, m_vectorLength);
-    for (; i < vectorEnd; ++i) {
-        WriteBarrier<Unknown>& v = vector[i];
-        if (!v)
-            break;
-        callFrame->setArgument(i, v.get());
-    }
-
-    for (; i < length; ++i)
-        callFrame->setArgument(i, get(exec, i));
-}
-
-unsigned JSArray::compactForSorting(JSGlobalData& globalData)
-{
-    ASSERT(!inSparseMode());
-
-    checkConsistency();
-
-    ArrayStorage* storage = m_storage;
-
-    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
-
-    unsigned numDefined = 0;
-    unsigned numUndefined = 0;
-
-    for (; numDefined < usedVectorLength; ++numDefined) {
-        JSValue v = storage->m_vector[numDefined].get();
-        if (!v || v.isUndefined())
-            break;
-    }
-
-    for (unsigned i = numDefined; i < usedVectorLength; ++i) {
-        JSValue v = storage->m_vector[i].get();
-        if (v) {
-            if (v.isUndefined())
-                ++numUndefined;
-            else
-                storage->m_vector[numDefined++].setWithoutWriteBarrier(v);
-        }
-    }
-
-    unsigned newUsedVectorLength = numDefined + numUndefined;
-
-    if (SparseArrayValueMap* map = m_sparseValueMap) {
-        newUsedVectorLength += map->size();
-        if (newUsedVectorLength > m_vectorLength) {
-            // Check that it is possible to allocate an array large enough to hold all the entries - if not,
-            // exception is thrown by caller.
-            if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(globalData, newUsedVectorLength))
-                return 0;
-
-            storage = m_storage;
-        }
-
-        SparseArrayValueMap::const_iterator end = map->end();
-        for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
-            storage->m_vector[numDefined++].setWithoutWriteBarrier(it->second.getNonSparseMode());
-
-        deallocateSparseMap();
-    }
-
-    for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
-        storage->m_vector[i].setUndefined();
-    for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
-        storage->m_vector[i].clear();
-
-    storage->m_numValuesInVector = newUsedVectorLength;
-
-    checkConsistency(SortConsistencyCheck);
-
-    return numDefined;
-}
-
-#if CHECK_ARRAY_CONSISTENCY
-
-void JSArray::checkConsistency(ConsistencyCheckType type)
-{
-    ArrayStorage* storage = m_storage;
-
-    ASSERT(!storage->m_inCompactInitialization);
-
-    ASSERT(storage);
-    if (type == SortConsistencyCheck)
-        ASSERT(!m_sparseValueMap);
-
-    unsigned numValuesInVector = 0;
-    for (unsigned i = 0; i < m_vectorLength; ++i) {
-        if (JSValue value = storage->m_vector[i].get()) {
-            ASSERT(i < storage->m_length);
-            if (type != DestructorConsistencyCheck)
-                value.isUndefined(); // Likely to crash if the object was deallocated.
-            ++numValuesInVector;
-        } else {
-            if (type == SortConsistencyCheck)
-                ASSERT(i >= storage->m_numValuesInVector);
-        }
-    }
-    ASSERT(numValuesInVector == storage->m_numValuesInVector);
-    ASSERT(numValuesInVector <= storage->m_length);
-
-    if (m_sparseValueMap) {
-        SparseArrayValueMap::const_iterator end = m_sparseValueMap->end();
-        for (SparseArrayValueMap::const_iterator it = m_sparseValueMap->begin(); it != end; ++it) {
-            unsigned index = it->first;
-            ASSERT(index < storage->m_length);
-            ASSERT(index >= m_vectorLength);
-            ASSERT(index <= MAX_ARRAY_INDEX);
-            ASSERT(it->second);
-            if (type != DestructorConsistencyCheck)
-                it->second.getNonSparseMode().isUndefined(); // Likely to crash if the object was deallocated.
-        }
-    }
-}
-
-#endif
+        
+        unsigned newUsedVectorLength = numDefined + numUndefined;
+        
+        if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
+            newUsedVectorLength += map->size();
+            if (newUsedVectorLength > storage->vectorLength()) {
+                // Check that it is possible to allocate an array large enough to hold all the entries - if not,
+                // exception is thrown by caller.
+                if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(globalData, newUsedVectorLength))
+                    return 0;
+                
+                storage = m_butterfly->arrayStorage();
+            }
+            
+            SparseArrayValueMap::const_iterator end = map->end();
+            for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
+                storage->m_vector[numDefined++].setWithoutWriteBarrier(it->second.getNonSparseMode());
+            
+            deallocateSparseIndexMap();
+        }
+        
+        for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
+            storage->m_vector[i].setUndefined();
+        for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
+            storage->m_vector[i].clear();
+        
+        storage->m_numValuesInVector = newUsedVectorLength;
+        
+        checkIndexingConsistency(SortConsistencyCheck);
+        
+        return numDefined;
+    }
+        
+    default:
+        ASSERT_NOT_REACHED();
+        return 0;
+    }
+}
+
 
 } // namespace JSC

trunk/Source/JavaScriptCore/runtime/JSArray.h

@@ -1 +1 @@
 /*
  *  Copyright (C) 1999-2000 Harri Porten ([email protected])
- *  Copyright (C) 2003, 2007, 2008, 2009 Apple Inc. All rights reserved.
+ *  Copyright (C) 2003, 2007, 2008, 2009, 2012 Apple Inc. All rights reserved.
  *
  *  This library is free software; you can redistribute it and/or
@@ -22 +22 @@
 #define JSArray_h
 
+#include "ArrayConventions.h"
+#include "ButterflyInlineMethods.h"
 #include "JSObject.h"
-
-#define CHECK_ARRAY_CONSISTENCY 0
 
 namespace JSC {
@@ -30 +30 @@
     class JSArray;
     class LLIntOffsetsExtractor;
-
-    enum PutDirectIndexMode { PutDirectIndexLikePutDirect, PutDirectIndexShouldNotThrow, PutDirectIndexShouldThrow };
-
-    struct SparseArrayEntry : public WriteBarrier<Unknown> {
-        typedef WriteBarrier<Unknown> Base;
-
-        SparseArrayEntry() : attributes(0) {}
-
-        JSValue get(ExecState*, JSArray*) const;
-        void get(PropertySlot&) const;
-        void get(PropertyDescriptor&) const;
-        JSValue getNonSparseMode() const;
-
-        unsigned attributes;
-    };
-
-    class SparseArrayValueMap {
-        typedef HashMap<uint64_t, SparseArrayEntry, WTF::IntHash<uint64_t>, WTF::UnsignedWithZeroKeyHashTraits<uint64_t> > Map;
-
-        enum Flags {
-            Normal = 0,
-            SparseMode = 1,
-            LengthIsReadOnly = 2,
-        };
-
-    public:
-        typedef Map::iterator iterator;
-        typedef Map::const_iterator const_iterator;
-        typedef Map::AddResult AddResult;
-
-        SparseArrayValueMap()
-            : m_flags(Normal)
-            , m_reportedCapacity(0)
-        {
-        }
-
-        void visitChildren(SlotVisitor&);
-
-        bool sparseMode()
-        {
-            return m_flags & SparseMode;
-        }
-
-        void setSparseMode()
-        {
-            m_flags = static_cast<Flags>(m_flags | SparseMode);
-        }
-
-        bool lengthIsReadOnly()
-        {
-            return m_flags & LengthIsReadOnly;
-        }
-
-        void setLengthIsReadOnly()
-        {
-            m_flags = static_cast<Flags>(m_flags | LengthIsReadOnly);
-        }
-
-        // These methods may mutate the contents of the map
-        void put(ExecState*, JSArray*, unsigned, JSValue, bool shouldThrow);
-        bool putDirect(ExecState*, JSArray*, unsigned, JSValue, PutDirectIndexMode);
-        AddResult add(JSArray*, unsigned);
-        iterator find(unsigned i) { return m_map.find(i); }
-        // This should ASSERT the remove is valid (check the result of the find).
-        void remove(iterator it) { m_map.remove(it); }
-        void remove(unsigned i) { m_map.remove(i); }
-
-        // These methods do not mutate the contents of the map.
-        iterator notFound() { return m_map.end(); }
-        bool isEmpty() const { return m_map.isEmpty(); }
-        bool contains(unsigned i) const { return m_map.contains(i); }
-        size_t size() const { return m_map.size(); }
-        // Only allow const begin/end iteration.
-        const_iterator begin() const { return m_map.begin(); }
-        const_iterator end() const { return m_map.end(); }
-
-    private:
-        Map m_map;
-        Flags m_flags;
-        size_t m_reportedCapacity;
-    };
-
-    // This struct holds the actual data values of an array.  A JSArray object points to it's contained ArrayStorage
-    // struct by pointing to m_vector.  To access the contained ArrayStorage struct, use the getStorage() and 
-    // setStorage() methods.  It is important to note that there may be space before the ArrayStorage that 
-    // is used to quick unshift / shift operation.  The actual allocated pointer is available by using:
-    //     getStorage() - m_indexBias * sizeof(JSValue)
-    struct ArrayStorage {
-        unsigned m_length; // The "length" property on the array
-        unsigned m_numValuesInVector;
-        void* m_allocBase; // Pointer to base address returned by malloc().  Keeping this pointer does eliminate false positives from the leak detector.
-#if CHECK_ARRAY_CONSISTENCY
-        // Needs to be a uintptr_t for alignment purposes.
-        uintptr_t m_initializationIndex;
-        uintptr_t m_inCompactInitialization;
-#else
-        uintptr_t m_padding;
-#endif
-        WriteBarrier<Unknown> m_vector[1];
-
-        static ptrdiff_t lengthOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_length); }
-        static ptrdiff_t numValuesInVectorOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_numValuesInVector); }
-        static ptrdiff_t allocBaseOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_allocBase); }
-        static ptrdiff_t vectorOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_vector); }
-    };
 
     class JSArray : public JSNonFinalObject {
@@ -141 +36 @@
         friend class JIT;
 
+    public:
+        typedef JSNonFinalObject Base;
+
     protected:
-        explicit JSArray(JSGlobalData& globalData, Structure* structure)
-            : JSNonFinalObject(globalData, structure)
-            , m_indexBias(0)
-            , m_storage(0)
-            , m_sparseValueMap(0)
+        explicit JSArray(JSGlobalData& globalData, Structure* structure, Butterfly* butterfly)
+            : JSNonFinalObject(globalData, structure, butterfly)
         {
         }
 
-        JS_EXPORT_PRIVATE void finishCreation(JSGlobalData&, unsigned initialLength = 0);
-        JS_EXPORT_PRIVATE JSArray* tryFinishCreationUninitialized(JSGlobalData&, unsigned initialLength);
-    
     public:
-        typedef JSNonFinalObject Base;
-
-        static void finalize(JSCell*);
-
         static JSArray* create(JSGlobalData&, Structure*, unsigned initialLength = 0);
 
@@ -170 +58 @@
 
         static bool getOwnPropertySlot(JSCell*, ExecState*, PropertyName, PropertySlot&);
-        JS_EXPORT_PRIVATE static bool getOwnPropertySlotByIndex(JSCell*, ExecState*, unsigned propertyName, PropertySlot&);
         static bool getOwnPropertyDescriptor(JSObject*, ExecState*, PropertyName, PropertyDescriptor&);
-        static void putByIndex(JSCell*, ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
-        // This is similar to the JSObject::putDirect* methods:
-        //  - the prototype chain is not consulted
-        //  - accessors are not called.
-        //  - it will ignore extensibility and read-only properties if PutDirectIndexLikePutDirect is passed as the mode (the default).
-        // This method creates a property with attributes writable, enumerable and configurable all set to true.
-        bool putDirectIndex(ExecState* exec, unsigned propertyName, JSValue value, PutDirectIndexMode mode = PutDirectIndexLikePutDirect)
-        {
-            if (canSetIndex(propertyName)) {
-                setIndex(exec->globalData(), propertyName, value);
-                return true;
-            }
-            return putDirectIndexBeyondVectorLength(exec, propertyName, value, mode);
-        }
 
         static JS_EXPORTDATA const ClassInfo s_info;
         
-        unsigned length() const { return m_storage->m_length; }
+        unsigned length() const { return getArrayLength(); }
         // OK to use on new arrays, but not if it might be a RegExpMatchArray.
         bool setLength(ExecState*, unsigned, bool throwException = false);
@@ -203 +76 @@
         bool unshiftCount(ExecState*, unsigned count);
 
-        bool canGetIndex(unsigned i) { return i < m_vectorLength && m_storage->m_vector[i]; }
-        JSValue getIndex(unsigned i)
-        {
-            ASSERT(canGetIndex(i));
-            return m_storage->m_vector[i].get();
-        }
-
-        bool canSetIndex(unsigned i) { return i < m_vectorLength; }
-        void setIndex(JSGlobalData& globalData, unsigned i, JSValue v)
-        {
-            ASSERT(canSetIndex(i));
-            
-            WriteBarrier<Unknown>& x = m_storage->m_vector[i];
-            if (!x) {
-                ArrayStorage *storage = m_storage;
-                ++storage->m_numValuesInVector;
-                if (i >= storage->m_length)
-                    storage->m_length = i + 1;
-            }
-            x.set(globalData, this, v);
-        }
-        
-        inline void initializeIndex(JSGlobalData& globalData, unsigned i, JSValue v)
-        {
-            ASSERT(canSetIndex(i));
-            ArrayStorage *storage = m_storage;
-#if CHECK_ARRAY_CONSISTENCY
-            ASSERT(storage->m_inCompactInitialization);
-            // Check that we are initializing the next index in sequence.
-            ASSERT(i == storage->m_initializationIndex);
-            // tryCreateUninitialized set m_numValuesInVector to the initialLength,
-            // check we do not try to initialize more than this number of properties.
-            ASSERT(storage->m_initializationIndex < storage->m_numValuesInVector);
-            storage->m_initializationIndex++;
-#endif
-            ASSERT(i < storage->m_length);
-            ASSERT(i < storage->m_numValuesInVector);
-            storage->m_vector[i].set(globalData, this, v);
-        }
-
-        inline void completeInitialization(unsigned newLength)
-        {
-            // Check that we have initialized as meny properties as we think we have.
-            ASSERT_UNUSED(newLength, newLength == m_storage->m_length);
-#if CHECK_ARRAY_CONSISTENCY
-            // Check that the number of propreties initialized matches the initialLength.
-            ASSERT(m_storage->m_initializationIndex == m_storage->m_numValuesInVector);
-            ASSERT(m_storage->m_inCompactInitialization);
-            m_storage->m_inCompactInitialization = false;
-#endif
-        }
-
-        bool inSparseMode()
-        {
-            SparseArrayValueMap* map = m_sparseValueMap;
-            return map && map->sparseMode();
-        }
-
         void fillArgList(ExecState*, MarkedArgumentBuffer&);
         void copyToArguments(ExecState*, CallFrame*, uint32_t length);
@@ -266 +81 @@
         static Structure* createStructure(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype)
         {
-            return Structure::create(globalData, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), &s_info);
+            return Structure::create(globalData, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), &s_info, ArrayWithArrayStorage);
         }
         
-        static ptrdiff_t storageOffset()
-        {
-            return OBJECT_OFFSETOF(JSArray, m_storage);
-        }
-
-        static ptrdiff_t vectorLengthOffset()
-        {
-            return OBJECT_OFFSETOF(JSArray, m_vectorLength);
-        }
-
-        JS_EXPORT_PRIVATE static void visitChildren(JSCell*, SlotVisitor&);
-
-        void enterDictionaryMode(JSGlobalData&);
-
     protected:
-        static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesVisitChildren | OverridesGetPropertyNames | JSObject::StructureFlags;
+        static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesGetPropertyNames | JSObject::StructureFlags;
         static void put(JSCell*, ExecState*, PropertyName, JSValue, PutPropertySlot&);
 
         static bool deleteProperty(JSCell*, ExecState*, PropertyName);
-        static bool deletePropertyByIndex(JSCell*, ExecState*, unsigned propertyName);
-        static void getOwnPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
+        JS_EXPORT_PRIVATE static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
 
     private:
-        static size_t storageSize(unsigned vectorLength);
         bool isLengthWritable()
         {
-            SparseArrayValueMap* map = m_sparseValueMap;
+            ArrayStorage* storage = arrayStorageOrNull();
+            if (!storage)
+                return false;
+            SparseArrayValueMap* map = storage->m_sparseMap.get();
             return !map || !map->lengthIsReadOnly();
         }
 
         void setLengthWritable(ExecState*, bool writable);
-        void putDescriptor(ExecState*, SparseArrayEntry*, PropertyDescriptor&, PropertyDescriptor& old);
-        bool defineOwnNumericProperty(ExecState*, unsigned, PropertyDescriptor&, bool throwException);
-        void allocateSparseMap(JSGlobalData&);
-        void deallocateSparseMap();
-
-        void putByIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
-        JS_EXPORT_PRIVATE bool putDirectIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, PutDirectIndexMode);
-
-        unsigned getNewVectorLength(unsigned desiredLength);
-        bool increaseVectorLength(JSGlobalData&, unsigned newLength);
+
         bool unshiftCountSlowCase(JSGlobalData&, unsigned count);
         
         unsigned compactForSorting(JSGlobalData&);
-
-        enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck };
-        void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck);
-
-        unsigned m_vectorLength; // The valid length of m_vector
-        unsigned m_indexBias; // The number of JSValue sized blocks before ArrayStorage.
-        ArrayStorage *m_storage;
-
-        // FIXME: Maybe SparseArrayValueMap should be put into its own JSCell?
-        SparseArrayValueMap* m_sparseValueMap;
-
-        static ptrdiff_t sparseValueMapOffset() { return OBJECT_OFFSETOF(JSArray, m_sparseValueMap); }
-        static ptrdiff_t indexBiasOffset() { return OBJECT_OFFSETOF(JSArray, m_indexBias); }
     };
 
+    inline Butterfly* createArrayButterfly(JSGlobalData& globalData, unsigned initialLength)
+    {
+        Butterfly* butterfly = Butterfly::create(
+            globalData, 0, 0, true, baseIndexingHeaderForArray(initialLength), ArrayStorage::sizeFor(BASE_VECTOR_LEN));
+        ArrayStorage* storage = butterfly->arrayStorage();
+        storage->m_indexBias = 0;
+        storage->m_sparseMap.clear();
+        storage->m_numValuesInVector = 0;
+#if CHECK_ARRAY_CONSISTENCY
+        storage->m_initializationIndex = 0;
+        storage->m_inCompactInitialization = 0;
+#endif
+        return butterfly;
+    }
+
+    Butterfly* createArrayButterflyInDictionaryIndexingMode(JSGlobalData&, unsigned initialLength);
+
     inline JSArray* JSArray::create(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
     {
-        JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
-        array->finishCreation(globalData, initialLength);
+        Butterfly* butterfly = createArrayButterfly(globalData, initialLength);
+        JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure, butterfly);
+        array->finishCreation(globalData);
         return array;
     }
@@ -337 +135 @@
     inline JSArray* JSArray::tryCreateUninitialized(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
     {
-        JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
-        return array->tryFinishCreationUninitialized(globalData, initialLength);
+        unsigned vectorLength = std::max(BASE_VECTOR_LEN, initialLength);
+        if (vectorLength > MAX_STORAGE_VECTOR_LENGTH)
+            return 0;
+        
+        void* temp;
+        if (!globalData.heap.tryAllocateStorage(Butterfly::totalSize(0, 0, true, ArrayStorage::sizeFor(vectorLength)), &temp))
+            return 0;
+        Butterfly* butterfly = Butterfly::fromBase(temp, 0, 0);
+        *butterfly->indexingHeader() = indexingHeaderForArray(initialLength, vectorLength);
+        ArrayStorage* storage = butterfly->arrayStorage();
+        storage->m_indexBias = 0;
+        storage->m_sparseMap.clear();
+        storage->m_numValuesInVector = initialLength;
+#if CHECK_ARRAY_CONSISTENCY
+        storage->m_initializationIndex = 0;
+        storage->m_inCompactInitialization = true;
+#endif
+        
+        JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure, butterfly);
+        array->finishCreation(globalData);
+        return array;
     }
 
@@ -356 +173 @@
     inline bool isJSArray(JSCell* cell) { return cell->classInfo() == &JSArray::s_info; }
     inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); }
-
-// The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
-// function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
-// size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) +
-// (vectorLength * sizeof(WriteBarrier<Unknown>)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
-#define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>))
-
-// These values have to be macros to be used in max() and min() without introducing
-// a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
-#define MIN_SPARSE_ARRAY_INDEX 10000U
-#define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
-    inline size_t JSArray::storageSize(unsigned vectorLength)
-    {
-        ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH);
-    
-        // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH)
-        // - as asserted above - the following calculation cannot overflow.
-        size_t size = (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) + (vectorLength * sizeof(WriteBarrier<Unknown>));
-        // Assertion to detect integer overflow in previous calculation (should not be possible, provided that
-        // MAX_STORAGE_VECTOR_LENGTH is correctly defined).
-        ASSERT(((size - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))));
-    
-        return size;
-    }
 
     inline JSArray* constructArray(ExecState* exec, Structure* arrayStructure, const ArgList& values)

trunk/Source/JavaScriptCore/runtime/JSBoundFunction.cpp

@@ -46 +46 @@
     MarkedArgumentBuffer args;
     for (unsigned i = 0; i < boundArgs->length(); ++i)
-        args.append(boundArgs->getIndex(i));
+        args.append(boundArgs->getIndexQuickly(i));
     for (unsigned i = 0; i < exec->argumentCount(); ++i)
         args.append(exec->argument(i));
@@ -66 +66 @@
     MarkedArgumentBuffer args;
     for (unsigned i = 0; i < boundArgs->length(); ++i)
-        args.append(boundArgs->getIndex(i));
+        args.append(boundArgs->getIndexQuickly(i));
     for (unsigned i = 0; i < exec->argumentCount(); ++i)
         args.append(exec->argument(i));
@@ -113 +113 @@
     ASSERT(inherits(&s_info));
 
-    putDirectAccessor(exec->globalData(), exec->propertyNames().arguments, globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
-    putDirectAccessor(exec->globalData(), exec->propertyNames().caller, globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
+    putDirectAccessor(exec, exec->propertyNames().arguments, globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
+    putDirectAccessor(exec, exec->propertyNames().caller, globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
 }
 

trunk/Source/JavaScriptCore/runtime/JSCell.cpp

@@ -179 +179 @@
 }
 
+void JSCell::getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode)
+{
+    ASSERT_NOT_REACHED();
+}
+
 String JSCell::className(const JSObject*)
 {

trunk/Source/JavaScriptCore/runtime/JSCell.h

@@ -139 +139 @@
             return &m_structure;
         }
-
+        
 #if ENABLE(GC_VALIDATION)
         Structure* unvalidatedStructure() { return m_structure.unvalidatedGet(); }
@@ -157 +157 @@
         static JSValue defaultValue(const JSObject*, ExecState*, PreferredPrimitiveType);
         static NO_RETURN_DUE_TO_ASSERT void getOwnPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
+        static NO_RETURN_DUE_TO_ASSERT void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
         static NO_RETURN_DUE_TO_ASSERT void getPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
         static String className(const JSObject*);

trunk/Source/JavaScriptCore/runtime/JSFunction.cpp

@@ -223 +223 @@
             bool result = Base::getOwnPropertySlot(thisObject, exec, propertyName, slot);
             if (!result) {
-                thisObject->putDirectAccessor(exec->globalData(), propertyName, thisObject->globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
+                thisObject->putDirectAccessor(exec, propertyName, thisObject->globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
                 result = Base::getOwnPropertySlot(thisObject, exec, propertyName, slot);
                 ASSERT(result);
@@ -247 +247 @@
             bool result = Base::getOwnPropertySlot(thisObject, exec, propertyName, slot);
             if (!result) {
-                thisObject->putDirectAccessor(exec->globalData(), propertyName, thisObject->globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
+                thisObject->putDirectAccessor(exec, propertyName, thisObject->globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
                 result = Base::getOwnPropertySlot(thisObject, exec, propertyName, slot);
                 ASSERT(result);
@@ -276 +276 @@
             bool result = Base::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor);
             if (!result) {
-                thisObject->putDirectAccessor(exec->globalData(), propertyName, thisObject->globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
+                thisObject->putDirectAccessor(exec, propertyName, thisObject->globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
                 result = Base::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor);
                 ASSERT(result);
@@ -300 +300 @@
             bool result = Base::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor);
             if (!result) {
-                thisObject->putDirectAccessor(exec->globalData(), propertyName, thisObject->globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
+                thisObject->putDirectAccessor(exec, propertyName, thisObject->globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
                 result = Base::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor);
                 ASSERT(result);
@@ -313 +313 @@
 }
 
-void JSFunction::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
+void JSFunction::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
 {
     JSFunction* thisObject = jsCast<JSFunction*>(object);
@@ -326 +326 @@
         propertyNames.add(exec->propertyNames().name);
     }
-    Base::getOwnPropertyNames(thisObject, exec, propertyNames, mode);
+    Base::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode);
 }
 
@@ -395 +395 @@
         if (thisObject->jsExecutable()->isStrictMode()) {
             if (!Base::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor))
-                thisObject->putDirectAccessor(exec->globalData(), propertyName, thisObject->globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
+                thisObject->putDirectAccessor(exec, propertyName, thisObject->globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
             return Base::defineOwnProperty(object, exec, propertyName, descriptor, throwException);
         }
@@ -402 +402 @@
         if (thisObject->jsExecutable()->isStrictMode()) {
             if (!Base::getOwnPropertyDescriptor(thisObject, exec, propertyName, descriptor))
-                thisObject->putDirectAccessor(exec->globalData(), propertyName, thisObject->globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
+                thisObject->putDirectAccessor(exec, propertyName, thisObject->globalObject()->throwTypeErrorGetterSetter(exec), DontDelete | DontEnum | Accessor);
             return Base::defineOwnProperty(object, exec, propertyName, descriptor, throwException);
         }

trunk/Source/JavaScriptCore/runtime/JSFunction.h

@@ -148 +148 @@
         static bool getOwnPropertySlot(JSCell*, ExecState*, PropertyName, PropertySlot&);
         static bool getOwnPropertyDescriptor(JSObject*, ExecState*, PropertyName, PropertyDescriptor&);
-        static void getOwnPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode = ExcludeDontEnumProperties);
+        static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode = ExcludeDontEnumProperties);
         static bool defineOwnProperty(JSObject*, ExecState*, PropertyName, PropertyDescriptor&, bool shouldThrow);
 

trunk/Source/JavaScriptCore/runtime/JSGlobalData.cpp

@@ -56 +56 @@
 #include "RegExpCache.h"
 #include "RegExpObject.h"
+#include "SparseArrayValueMapInlineMethods.h"
 #include "StrictEvalActivation.h"
 #include "StrongInlines.h"
@@ -214 +215 @@
     sharedSymbolTableStructure.set(*this, SharedSymbolTable::createStructure(*this, 0, jsNull()));
     structureChainStructure.set(*this, StructureChain::createStructure(*this, 0, jsNull()));
+    sparseArrayValueMapStructure.set(*this, SparseArrayValueMap::createStructure(*this, 0, jsNull()));
 
     wtfThreadData().setCurrentIdentifierTable(existingEntryIdentifierTable);

trunk/Source/JavaScriptCore/runtime/JSGlobalData.h

@@ -245 +245 @@
         Strong<Structure> sharedSymbolTableStructure;
         Strong<Structure> structureChainStructure;
+        Strong<Structure> sparseArrayValueMapStructure;
 
         IdentifierTable* identifierTable;

trunk/Source/JavaScriptCore/runtime/JSGlobalObject.cpp

@@ -214 +214 @@
     protoAccessor->setGetter(exec->globalData(), JSFunction::create(exec, this, 0, String(), globalFuncProtoGetter));
     protoAccessor->setSetter(exec->globalData(), JSFunction::create(exec, this, 0, String(), globalFuncProtoSetter));
-    m_objectPrototype->putDirectAccessor(exec->globalData(), exec->propertyNames().underscoreProto, protoAccessor, Accessor | DontEnum);
+    m_objectPrototype->putDirectAccessor(exec, exec->propertyNames().underscoreProto, protoAccessor, Accessor | DontEnum);
     m_functionPrototype->structure()->setPrototypeWithoutTransition(exec->globalData(), m_objectPrototype.get());
 

trunk/Source/JavaScriptCore/runtime/JSONObject.cpp

@@ -522 +522 @@
         // Get the value.
         JSValue value;
-        if (m_isJSArray && asArray(m_object.get())->canGetIndex(index))
-            value = asArray(m_object.get())->getIndex(index);
+        if (m_isJSArray && asArray(m_object.get())->canGetIndexQuickly(index))
+            value = asArray(m_object.get())->getIndexQuickly(index);
         else {
             PropertySlot slot(m_object.get());
@@ -688 +688 @@
                     break;
                 }
-                if (isJSArray(array) && array->canGetIndex(index))
-                    inValue = array->getIndex(index);
+                if (isJSArray(array) && array->canGetIndexQuickly(index))
+                    inValue = array->getIndexQuickly(index);
                 else {
                     PropertySlot slot;

trunk/Source/JavaScriptCore/runtime/JSObject.cpp

@@ -2 +2 @@
  *  Copyright (C) 1999-2001 Harri Porten ([email protected])
  *  Copyright (C) 2001 Peter Kelly ([email protected])
- *  Copyright (C) 2003, 2004, 2005, 2006, 2008, 2009 Apple Inc. All rights reserved.
+ *  Copyright (C) 2003, 2004, 2005, 2006, 2008, 2009, 2012 Apple Inc. All rights reserved.
  *  Copyright (C) 2007 Eric Seidel ([email protected])
  *
@@ -25 +25 @@
 #include "JSObject.h"
 
+#include "ButterflyInlineMethods.h"
 #include "CopiedSpaceInlineMethods.h"
 #include "DatePrototype.h"
 #include "ErrorConstructor.h"
 #include "GetterSetter.h"
+#include "IndexingHeaderInlineMethods.h"
 #include "JSFunction.h"
 #include "JSGlobalObject.h"
@@ -39 +41 @@
 #include "PropertyDescriptor.h"
 #include "PropertyNameArray.h"
+#include "Reject.h"
 #include "SlotVisitorInlineMethods.h"
+#include "SparseArrayValueMapInlineMethods.h"
 #include <math.h>
 #include <wtf/Assertions.h>
 
 namespace JSC {
+
+// We keep track of the size of the last array after it was grown. We use this
+// as a simple heuristic for as the value to grow the next array from size 0.
+// This value is capped by the constant FIRST_VECTOR_GROW defined above.
+static unsigned lastArraySize = 0;
 
 JSCell* getCallableObjectSlow(JSCell* cell)
@@ -87 +96 @@
 }
 
-ALWAYS_INLINE void JSObject::visitOutOfLineStorage(SlotVisitor& visitor, PropertyStorage storage, size_t storageSize)
-{
-    ASSERT(storage);
-    ASSERT(storageSize);
-    
-    size_t capacity = structure()->outOfLineCapacity();
-    ASSERT(capacity);
-    size_t capacityInBytes = capacity * sizeof(WriteBarrierBase<Unknown>);
-    PropertyStorage baseOfStorage = storage - capacity - 1;
-    if (visitor.checkIfShouldCopyAndPinOtherwise(baseOfStorage, capacityInBytes)) {
-        PropertyStorage newBaseOfStorage = static_cast<PropertyStorage>(visitor.allocateNewSpace(capacityInBytes));
-        PropertyStorage currentTarget = newBaseOfStorage + capacity;
-        PropertyStorage newStorage = currentTarget + 1;
-        PropertyStorage currentSource = storage - 1;
+ALWAYS_INLINE void JSObject::visitButterfly(SlotVisitor& visitor, Butterfly* butterfly, size_t storageSize)
+{
+    ASSERT(butterfly);
+    
+    Structure* structure = this->structure();
+    
+    size_t propertyCapacity = structure->outOfLineCapacity();
+    size_t preCapacity;
+    size_t indexingPayloadSizeInBytes;
+    bool hasIndexingHeader = JSC::hasIndexingHeader(structure->indexingType());
+    if (UNLIKELY(hasIndexingHeader)) {
+        preCapacity = butterfly->indexingHeader()->preCapacity(structure);
+        indexingPayloadSizeInBytes = butterfly->indexingHeader()->indexingPayloadSizeInBytes(structure);
+    } else {
+        preCapacity = 0;
+        indexingPayloadSizeInBytes = 0;
+    }
+    size_t capacityInBytes = Butterfly::totalSize(
+        preCapacity, propertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes);
+    if (visitor.checkIfShouldCopyAndPinOtherwise(
+            butterfly->base(preCapacity, propertyCapacity), capacityInBytes)) {
+        Butterfly* newButterfly = Butterfly::createUninitializedDuringCollection(visitor, preCapacity, propertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes);
+        
+        // Mark and copy the properties.
+        PropertyStorage currentTarget = newButterfly->propertyStorage();
+        PropertyStorage currentSource = butterfly->propertyStorage();
         for (size_t count = storageSize; count--;) {
             JSValue value = (--currentSource)->get();
@@ -107 +128 @@
             (--currentTarget)->setWithoutWriteBarrier(value);
         }
-        m_outOfLineStorage.set(newStorage, StorageBarrier::Unchecked);
-    } else
-        visitor.appendValues(storage - storageSize - 1, storageSize);
+        
+        if (UNLIKELY(hasIndexingHeader)) {
+            *newButterfly->indexingHeader() = *butterfly->indexingHeader();
+            
+            // Mark and copy the array if appropriate.
+            switch (structure->indexingType()) {
+            case ArrayWithArrayStorage:
+            case NonArrayWithArrayStorage: {
+                newButterfly->arrayStorage()->copyHeaderFromDuringGC(*butterfly->arrayStorage());
+                WriteBarrier<Unknown>* currentTarget = newButterfly->arrayStorage()->m_vector;
+                WriteBarrier<Unknown>* currentSource = butterfly->arrayStorage()->m_vector;
+                for (size_t count = newButterfly->arrayStorage()->vectorLength(); count--;) {
+                    JSValue value = (currentSource++)->get();
+                    if (value)
+                        visitor.appendUnbarrieredValue(&value);
+                    (currentTarget++)->setWithoutWriteBarrier(value);
+                }
+                if (newButterfly->arrayStorage()->m_sparseMap)
+                    visitor.append(&newButterfly->arrayStorage()->m_sparseMap);
+                break;
+            }
+            default:
+                break;
+            }
+        }
+        
+        m_butterfly = newButterfly;
+    } else {
+        // Mark the properties.
+        visitor.appendValues(butterfly->propertyStorage() - storageSize, storageSize);
+        
+        // Mark the array if appropriate.
+        switch (structure->indexingType()) {
+        case ArrayWithArrayStorage:
+        case NonArrayWithArrayStorage:
+            visitor.appendValues(butterfly->arrayStorage()->m_vector, butterfly->arrayStorage()->vectorLength());
+            if (butterfly->arrayStorage()->m_sparseMap)
+                visitor.append(&butterfly->arrayStorage()->m_sparseMap);
+            break;
+        default:
+            break;
+        }
+    }
 }
 
@@ -123 +184 @@
     JSCell::visitChildren(thisObject, visitor);
 
-    PropertyStorage storage = thisObject->outOfLineStorage();
-    if (storage)
-        thisObject->visitOutOfLineStorage(visitor, storage, thisObject->structure()->outOfLineSizeForKnownNonFinalObject());
+    Butterfly* butterfly = thisObject->butterfly();
+    if (butterfly)
+        thisObject->visitButterfly(visitor, butterfly, thisObject->structure()->outOfLineSizeForKnownNonFinalObject());
 
 #if !ASSERT_DISABLED
@@ -143 +204 @@
     JSCell::visitChildren(thisObject, visitor);
 
-    PropertyStorage storage = thisObject->outOfLineStorage();
-    if (storage)
-        thisObject->visitOutOfLineStorage(visitor, storage, thisObject->structure()->outOfLineSizeForKnownFinalObject());
+    Butterfly* butterfly = thisObject->butterfly();
+    if (butterfly)
+        thisObject->visitButterfly(visitor, butterfly, thisObject->structure()->outOfLineSizeForKnownFinalObject());
 
     size_t storageSize = thisObject->structure()->inlineSizeForKnownFinalObject();
@@ -162 +223 @@
 }
 
-bool JSObject::getOwnPropertySlotByIndex(JSCell* cell, ExecState* exec, unsigned propertyName, PropertySlot& slot)
-{
+bool JSObject::getOwnPropertySlotByIndex(JSCell* cell, ExecState* exec, unsigned i, PropertySlot& slot)
+{
+    // NB. The fact that we're directly consulting our indexed storage implies that it is not
+    // legal for anyone to override getOwnPropertySlot() without also overriding
+    // getOwnPropertySlotByIndex().
+    
     JSObject* thisObject = jsCast<JSObject*>(cell);
-    return thisObject->methodTable()->getOwnPropertySlot(thisObject, exec, Identifier::from(exec, propertyName), slot);
+    
+    if (i > MAX_ARRAY_INDEX)
+        return thisObject->methodTable()->getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
+    
+    switch (thisObject->structure()->indexingType()) {
+    case NonArray:
+    case Array:
+        break;
+        
+    case NonArrayWithArrayStorage:
+    case ArrayWithArrayStorage: {
+        ArrayStorage* storage = thisObject->m_butterfly->arrayStorage();
+        if (i >= storage->length())
+            return false;
+        
+        if (i < storage->vectorLength()) {
+            JSValue value = storage->m_vector[i].get();
+            if (value) {
+                slot.setValue(value);
+                return true;
+            }
+        } else if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
+            SparseArrayValueMap::iterator it = map->find(i);
+            if (it != map->notFound()) {
+                it->second.get(slot);
+                return true;
+            }
+        }
+        break;
+    }
+        
+    default:
+        ASSERT_NOT_REACHED();
+        break;
+    }
+    
+    return false;
 }
 
@@ -175 +276 @@
     ASSERT(!Heap::heap(value) || Heap::heap(value) == Heap::heap(thisObject));
     JSGlobalData& globalData = exec->globalData();
+    
+    // Try indexed put first. This is required for correctness, since loads on property names that appear like
+    // valid indices will never look in the named property storage.
+    unsigned i = propertyName.asIndex();
+    if (i != PropertyName::NotAnIndex) {
+        putByIndex(thisObject, exec, i, value, slot.isStrictMode());
+        return;
+    }
 
     // Check if there are any setters or getters in the prototype chain
@@ -236 +345 @@
 void JSObject::putByIndex(JSCell* cell, ExecState* exec, unsigned propertyName, JSValue value, bool shouldThrow)
 {
-    PutPropertySlot slot(shouldThrow);
     JSObject* thisObject = jsCast<JSObject*>(cell);
-    thisObject->methodTable()->put(thisObject, exec, Identifier::from(exec, propertyName), value, slot);
+    thisObject->checkIndexingConsistency();
+    
+    if (UNLIKELY(propertyName > MAX_ARRAY_INDEX)) {
+        PutPropertySlot slot(shouldThrow);
+        thisObject->methodTable()->put(thisObject, exec, Identifier::from(exec, propertyName), value, slot);
+        return;
+    }
+    
+    switch (thisObject->structure()->indexingType()) {
+    case NonArray:
+    case Array:
+        break;
+        
+    case NonArrayWithArrayStorage:
+    case ArrayWithArrayStorage: {
+        ArrayStorage* storage = thisObject->m_butterfly->arrayStorage();
+        
+        if (propertyName >= storage->vectorLength())
+            break;
+        
+        WriteBarrier<Unknown>& valueSlot = storage->m_vector[propertyName];
+        unsigned length = storage->length();
+        
+        // Update length & m_numValuesInVector as necessary.
+        if (propertyName >= length) {
+            length = propertyName + 1;
+            storage->setLength(length);
+            ++storage->m_numValuesInVector;
+        } else if (!valueSlot)
+            ++storage->m_numValuesInVector;
+        
+        valueSlot.set(exec->globalData(), thisObject, value);
+        thisObject->checkIndexingConsistency();
+        return;
+    }
+        
+    default:
+        ASSERT_NOT_REACHED();
+    }
+    
+    thisObject->putByIndexBeyondVectorLength(exec, propertyName, value, shouldThrow);
+    thisObject->checkIndexingConsistency();
+}
+
+ArrayStorage* JSObject::enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(JSGlobalData& globalData, ArrayStorage* storage)
+{
+    SparseArrayValueMap* map = storage->m_sparseMap.get();
+
+    if (!map)
+        map = allocateSparseIndexMap(globalData);
+
+    if (map->sparseMode())
+        return storage;
+
+    map->setSparseMode();
+
+    unsigned usedVectorLength = std::min(storage->length(), storage->vectorLength());
+    for (unsigned i = 0; i < usedVectorLength; ++i) {
+        JSValue value = storage->m_vector[i].get();
+        // This will always be a new entry in the map, so no need to check we can write,
+        // and attributes are default so no need to set them.
+        if (value)
+            map->add(this, i).iterator->second.set(globalData, this, value);
+    }
+
+    Butterfly* newButterfly = storage->butterfly()->resizeArray(globalData, structure(), 0, ArrayStorage::sizeFor(0));
+    if (!newButterfly)
+        CRASH();
+    
+    m_butterfly = newButterfly;
+    newButterfly->arrayStorage()->m_indexBias = 0;
+    newButterfly->arrayStorage()->setVectorLength(0);
+    newButterfly->arrayStorage()->m_sparseMap.set(globalData, this, map);
+    
+    return newButterfly->arrayStorage();
+}
+
+void JSObject::enterDictionaryIndexingMode(JSGlobalData& globalData)
+{
+    switch (structure()->indexingType()) {
+    case ArrayWithArrayStorage:
+    case NonArrayWithArrayStorage:
+        enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(globalData, m_butterfly->arrayStorage());
+        break;
+        
+    default:
+        break;
+    }
+}
+
+ArrayStorage* JSObject::createArrayStorage(JSGlobalData& globalData, unsigned length, unsigned vectorLength)
+{
+    IndexingType oldType = structure()->indexingType();
+    ASSERT_UNUSED(oldType, oldType == NonArray || oldType == Array);
+    Butterfly* newButterfly = m_butterfly->growArrayRight(
+        globalData, structure(), structure()->outOfLineCapacity(), false, 0,
+        ArrayStorage::sizeFor(vectorLength));
+    if (!newButterfly)
+        CRASH();
+    ArrayStorage* result = newButterfly->arrayStorage();
+    result->setLength(length);
+    result->setVectorLength(vectorLength);
+    result->m_sparseMap.clear();
+    result->m_numValuesInVector = 0;
+    result->m_indexBias = 0;
+#if CHECK_ARRAY_CONSISTENCY
+    result->m_initializationIndex = 0;
+    result->m_inCompactInitialization = 0;
+#endif
+    Structure* newStructure = Structure::nonPropertyTransition(globalData, structure(), AllocateArrayStorage);
+    setButterfly(globalData, newButterfly, newStructure);
+    return result;
+}
+
+ArrayStorage* JSObject::createInitialArrayStorage(JSGlobalData& globalData)
+{
+    return createArrayStorage(globalData, 0, BASE_VECTOR_LEN);
+}
+
+ArrayStorage* JSObject::ensureArrayStorageExistsAndEnterDictionaryIndexingMode(JSGlobalData& globalData)
+{
+    switch (structure()->indexingType()) {
+    case ArrayWithArrayStorage:
+    case NonArrayWithArrayStorage:
+        return enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(globalData, m_butterfly->arrayStorage());
+        
+    case Array:
+    case NonArray: {
+        createArrayStorage(globalData, 0, 0);
+        SparseArrayValueMap* map = allocateSparseIndexMap(globalData);
+        map->setSparseMode();
+        return arrayStorage();
+    }
+        
+    default:
+        ASSERT_NOT_REACHED();
+        return 0;
+    }
 }
 
@@ -270 +515 @@
 }
 
-void JSObject::putDirectAccessor(JSGlobalData& globalData, PropertyName propertyName, JSValue value, unsigned attributes)
+void JSObject::putDirectAccessor(ExecState* exec, PropertyName propertyName, JSValue value, unsigned attributes)
 {
     ASSERT(value.isGetterSetter() && (attributes & Accessor));
+
+    unsigned index = propertyName.asIndex();
+    if (index != PropertyName::NotAnIndex) {
+        putDirectIndex(exec, index, value, attributes, PutDirectIndexLikePutDirect);
+        return;
+    }
+
+    JSGlobalData& globalData = exec->globalData();
 
     PutPropertySlot slot;
@@ -305 +558 @@
 {
     JSObject* thisObject = jsCast<JSObject*>(cell);
+    
+    unsigned i = propertyName.asIndex();
+    if (i != PropertyName::NotAnIndex)
+        return thisObject->methodTable()->deletePropertyByIndex(thisObject, exec, i);
 
     if (!thisObject->staticFunctionsReified())
@@ -333 +590 @@
 }
 
-bool JSObject::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned propertyName)
+bool JSObject::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned i)
 {
     JSObject* thisObject = jsCast<JSObject*>(cell);
-    return thisObject->methodTable()->deleteProperty(thisObject, exec, Identifier::from(exec, propertyName));
+    
+    if (i > MAX_ARRAY_INDEX)
+        return thisObject->methodTable()->deleteProperty(thisObject, exec, Identifier::from(exec, i));
+    
+    switch (thisObject->structure()->indexingType()) {
+    case Array:
+    case NonArray:
+        return true;
+        
+    case ArrayWithArrayStorage:
+    case NonArrayWithArrayStorage: {
+        ArrayStorage* storage = thisObject->m_butterfly->arrayStorage();
+        
+        if (i < storage->vectorLength()) {
+            WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
+            if (valueSlot) {
+                valueSlot.clear();
+                --storage->m_numValuesInVector;
+            }
+        } else if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
+            SparseArrayValueMap::iterator it = map->find(i);
+            if (it != map->notFound()) {
+                if (it->second.attributes & DontDelete)
+                    return false;
+                map->remove(it);
+            }
+        }
+        
+        thisObject->checkIndexingConsistency();
+        return true;
+    }
+        
+    default:
+        ASSERT_NOT_REACHED();
+        return false;
+    }
 }
 
@@ -466 +758 @@
 void JSObject::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
 {
+    // Add numeric properties first. That appears to be the accepted convention.
+    // FIXME: Filling PropertyNameArray with an identifier for every integer
+    // is incredibly inefficient for large arrays. We need a different approach,
+    // which almost certainly means a different structure for PropertyNameArray.
+    switch (object->structure()->indexingType()) {
+    case NonArray:
+    case Array:
+        break;
+        
+    case NonArrayWithArrayStorage:
+    case ArrayWithArrayStorage: {
+        ArrayStorage* storage = object->m_butterfly->arrayStorage();
+        
+        unsigned usedVectorLength = std::min(storage->length(), storage->vectorLength());
+        for (unsigned i = 0; i < usedVectorLength; ++i) {
+            if (storage->m_vector[i])
+                propertyNames.add(Identifier::from(exec, i));
+        }
+        
+        if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
+            Vector<unsigned> keys;
+            keys.reserveCapacity(map->size());
+            
+            SparseArrayValueMap::const_iterator end = map->end();
+            for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
+                if (mode == IncludeDontEnumProperties || !(it->second.attributes & DontEnum))
+                    keys.append(static_cast<unsigned>(it->first));
+            }
+            
+            std::sort(keys.begin(), keys.end());
+            for (unsigned i = 0; i < keys.size(); ++i)
+                propertyNames.add(Identifier::from(exec, keys[i]));
+        }
+        break;
+    }
+        
+    default:
+        ASSERT_NOT_REACHED();
+    }
+    
+    object->methodTable()->getOwnNonIndexPropertyNames(object, exec, propertyNames, mode);
+}
+
+void JSObject::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
+{
     getClassPropertyNames(exec, object->classInfo(), propertyNames, mode, object->staticFunctionsReified());
     object->structure()->getPropertyNamesFromStructure(exec->globalData(), propertyNames, mode);
@@ -516 +853 @@
 void JSObject::preventExtensions(JSGlobalData& globalData)
 {
-    if (isJSArray(this))
-        asArray(this)->enterDictionaryMode(globalData);
+    enterDictionaryIndexingMode(globalData);
     if (isExtensible())
         setStructure(globalData, Structure::preventExtensionsTransition(globalData, structure()));
@@ -574 +910 @@
 }
 
-NEVER_INLINE void JSObject::fillGetterPropertySlot(PropertySlot& slot, WriteBarrierBase<Unknown>* location)
-{
-    if (JSObject* getterFunction = asGetterSetter(location->get())->getter()) {
+NEVER_INLINE void JSObject::fillGetterPropertySlot(PropertySlot& slot, PropertyOffset offset)
+{
+    if (JSObject* getterFunction = asGetterSetter(getDirectOffset(offset))->getter()) {
         if (!structure()->isDictionary())
-            slot.setCacheableGetterSlot(this, getterFunction, offsetForLocation(location));
+            slot.setCacheableGetterSlot(this, getterFunction, offset);
         else
             slot.setGetterSlot(getterFunction);
@@ -604 +940 @@
 }
 
-PropertyStorage JSObject::growOutOfLineStorage(JSGlobalData& globalData, size_t oldSize, size_t newSize)
+void JSObject::putIndexedDescriptor(ExecState* exec, SparseArrayEntry* entryInMap, PropertyDescriptor& descriptor, PropertyDescriptor& oldDescriptor)
+{
+    if (descriptor.isDataDescriptor()) {
+        if (descriptor.value())
+            entryInMap->set(exec->globalData(), this, descriptor.value());
+        else if (oldDescriptor.isAccessorDescriptor())
+            entryInMap->set(exec->globalData(), this, jsUndefined());
+        entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor) & ~Accessor;
+        return;
+    }
+
+    if (descriptor.isAccessorDescriptor()) {
+        JSObject* getter = 0;
+        if (descriptor.getterPresent())
+            getter = descriptor.getterObject();
+        else if (oldDescriptor.isAccessorDescriptor())
+            getter = oldDescriptor.getterObject();
+        JSObject* setter = 0;
+        if (descriptor.setterPresent())
+            setter = descriptor.setterObject();
+        else if (oldDescriptor.isAccessorDescriptor())
+            setter = oldDescriptor.setterObject();
+
+        GetterSetter* accessor = GetterSetter::create(exec);
+        if (getter)
+            accessor->setGetter(exec->globalData(), getter);
+        if (setter)
+            accessor->setSetter(exec->globalData(), setter);
+
+        entryInMap->set(exec->globalData(), this, accessor);
+        entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor) & ~ReadOnly;
+        return;
+    }
+
+    ASSERT(descriptor.isGenericDescriptor());
+    entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor);
+}
+
+// Defined in ES5.1 8.12.9
+bool JSObject::defineOwnIndexedProperty(ExecState* exec, unsigned index, PropertyDescriptor& descriptor, bool throwException)
+{
+    ASSERT(index != 0xFFFFFFFF);
+
+    if (!inSparseIndexingMode()) {
+        // Fast case: we're putting a regular property to a regular array
+        // FIXME: this will pessimistically assume that if attributes are missing then they'll default to false
+        // however if the property currently exists missing attributes will override from their current 'true'
+        // state (i.e. defineOwnProperty could be used to set a value without needing to entering 'SparseMode').
+        if (!descriptor.attributes()) {
+            ASSERT(!descriptor.isAccessorDescriptor());
+            return putDirectIndex(exec, index, descriptor.value(), 0, throwException ? PutDirectIndexShouldThrow : PutDirectIndexShouldNotThrow);
+        }
+
+        ensureArrayStorageExistsAndEnterDictionaryIndexingMode(exec->globalData());
+    }
+
+    SparseArrayValueMap* map = m_butterfly->arrayStorage()->m_sparseMap.get();
+    ASSERT(map);
+
+    // 1. Let current be the result of calling the [[GetOwnProperty]] internal method of O with property name P.
+    SparseArrayValueMap::AddResult result = map->add(this, index);
+    SparseArrayEntry* entryInMap = &result.iterator->second;
+
+    // 2. Let extensible be the value of the [[Extensible]] internal property of O.
+    // 3. If current is undefined and extensible is false, then Reject.
+    // 4. If current is undefined and extensible is true, then
+    if (result.isNewEntry) {
+        if (!isExtensible()) {
+            map->remove(result.iterator);
+            return reject(exec, throwException, "Attempting to define property on object that is not extensible.");
+        }
+
+        // 4.a. If IsGenericDescriptor(Desc) or IsDataDescriptor(Desc) is true, then create an own data property
+        // named P of object O whose [[Value]], [[Writable]], [[Enumerable]] and [[Configurable]] attribute values
+        // are described by Desc. If the value of an attribute field of Desc is absent, the attribute of the newly
+        // created property is set to its default value.
+        // 4.b. Else, Desc must be an accessor Property Descriptor so, create an own accessor property named P of
+        // object O whose [[Get]], [[Set]], [[Enumerable]] and [[Configurable]] attribute values are described by
+        // Desc. If the value of an attribute field of Desc is absent, the attribute of the newly created property
+        // is set to its default value.
+        // 4.c. Return true.
+
+        PropertyDescriptor defaults;
+        entryInMap->setWithoutWriteBarrier(jsUndefined());
+        entryInMap->attributes = DontDelete | DontEnum | ReadOnly;
+        entryInMap->get(defaults);
+
+        putIndexedDescriptor(exec, entryInMap, descriptor, defaults);
+        if (index >= m_butterfly->arrayStorage()->length())
+            m_butterfly->arrayStorage()->setLength(index + 1);
+        return true;
+    }
+
+    // 5. Return true, if every field in Desc is absent.
+    // 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).
+    PropertyDescriptor current;
+    entryInMap->get(current);
+    if (descriptor.isEmpty() || descriptor.equalTo(exec, current))
+        return true;
+
+    // 7. If the [[Configurable]] field of current is false then
+    if (!current.configurable()) {
+        // 7.a. Reject, if the [[Configurable]] field of Desc is true.
+        if (descriptor.configurablePresent() && descriptor.configurable())
+            return reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property.");
+        // 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.
+        if (descriptor.enumerablePresent() && current.enumerable() != descriptor.enumerable())
+            return reject(exec, throwException, "Attempting to change enumerable attribute of unconfigurable property.");
+    }
+
+    // 8. If IsGenericDescriptor(Desc) is true, then no further validation is required.
+    if (!descriptor.isGenericDescriptor()) {
+        // 9. Else, if IsDataDescriptor(current) and IsDataDescriptor(Desc) have different results, then
+        if (current.isDataDescriptor() != descriptor.isDataDescriptor()) {
+            // 9.a. Reject, if the [[Configurable]] field of current is false.
+            if (!current.configurable())
+                return reject(exec, throwException, "Attempting to change access mechanism for an unconfigurable property.");
+            // 9.b. If IsDataDescriptor(current) is true, then convert the property named P of object O from a
+            // data property to an accessor property. Preserve the existing values of the converted property's
+            // [[Configurable]] and [[Enumerable]] attributes and set the rest of the property's attributes to
+            // their default values.
+            // 9.c. Else, convert the property named P of object O from an accessor property to a data property.
+            // Preserve the existing values of the converted property's [[Configurable]] and [[Enumerable]]
+            // attributes and set the rest of the property's attributes to their default values.
+        } else if (current.isDataDescriptor() && descriptor.isDataDescriptor()) {
+            // 10. Else, if IsDataDescriptor(current) and IsDataDescriptor(Desc) are both true, then
+            // 10.a. If the [[Configurable]] field of current is false, then
+            if (!current.configurable() && !current.writable()) {
+                // 10.a.i. Reject, if the [[Writable]] field of current is false and the [[Writable]] field of Desc is true.
+                if (descriptor.writable())
+                    return reject(exec, throwException, "Attempting to change writable attribute of unconfigurable property.");
+                // 10.a.ii. If the [[Writable]] field of current is false, then
+                // 10.a.ii.1. Reject, if the [[Value]] field of Desc is present and SameValue(Desc.[[Value]], current.[[Value]]) is false.
+                if (descriptor.value() && !sameValue(exec, descriptor.value(), current.value()))
+                    return reject(exec, throwException, "Attempting to change value of a readonly property.");
+            }
+            // 10.b. else, the [[Configurable]] field of current is true, so any change is acceptable.
+        } else {
+            ASSERT(current.isAccessorDescriptor() && current.getterPresent() && current.setterPresent());
+            // 11. Else, IsAccessorDescriptor(current) and IsAccessorDescriptor(Desc) are both true so, if the [[Configurable]] field of current is false, then
+            if (!current.configurable()) {
+                // 11.i. Reject, if the [[Set]] field of Desc is present and SameValue(Desc.[[Set]], current.[[Set]]) is false.
+                if (descriptor.setterPresent() && descriptor.setter() != current.setter())
+                    return reject(exec, throwException, "Attempting to change the setter of an unconfigurable property.");
+                // 11.ii. Reject, if the [[Get]] field of Desc is present and SameValue(Desc.[[Get]], current.[[Get]]) is false.
+                if (descriptor.getterPresent() && descriptor.getter() != current.getter())
+                    return reject(exec, throwException, "Attempting to change the getter of an unconfigurable property.");
+            }
+        }
+    }
+
+    // 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.
+    putIndexedDescriptor(exec, entryInMap, descriptor, current);
+    // 13. Return true.
+    return true;
+}
+
+SparseArrayValueMap* JSObject::allocateSparseIndexMap(JSGlobalData& globalData)
+{
+    SparseArrayValueMap* result = SparseArrayValueMap::create(globalData);
+    arrayStorage()->m_sparseMap.set(globalData, this, result);
+    return result;
+}
+
+void JSObject::deallocateSparseIndexMap()
+{
+    if (ArrayStorage* arrayStorage = arrayStorageOrNull())
+        arrayStorage->m_sparseMap.clear();
+}
+
+void JSObject::putByIndexBeyondVectorLengthWithArrayStorage(ExecState* exec, unsigned i, JSValue value, bool shouldThrow, ArrayStorage* storage)
+{
+    JSGlobalData& globalData = exec->globalData();
+
+    // i should be a valid array index that is outside of the current vector.
+    ASSERT(i <= MAX_ARRAY_INDEX);
+    ASSERT(i >= storage->vectorLength());
+    
+    SparseArrayValueMap* map = storage->m_sparseMap.get();
+    
+    // First, handle cases where we don't currently have a sparse map.
+    if (LIKELY(!map)) {
+        // If the array is not extensible, we should have entered dictionary mode, and created the spare map.
+        ASSERT(isExtensible());
+    
+        // Update m_length if necessary.
+        if (i >= storage->length())
+            storage->setLength(i + 1);
+
+        // Check that it is sensible to still be using a vector, and then try to grow the vector.
+        if (LIKELY((isDenseEnoughForVector(i, storage->m_numValuesInVector)) && increaseVectorLength(globalData, i + 1))) {
+            // success! - reread m_storage since it has likely been reallocated, and store to the vector.
+            storage = arrayStorage();
+            storage->m_vector[i].set(globalData, this, value);
+            ++storage->m_numValuesInVector;
+            return;
+        }
+        // We don't want to, or can't use a vector to hold this property - allocate a sparse map & add the value.
+        map = allocateSparseIndexMap(exec->globalData());
+        map->putEntry(exec, this, i, value, shouldThrow);
+        return;
+    }
+
+    // Update m_length if necessary.
+    unsigned length = storage->length();
+    if (i >= length) {
+        // Prohibit growing the array if length is not writable.
+        if (map->lengthIsReadOnly() || !isExtensible()) {
+            if (shouldThrow)
+                throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
+            return;
+        }
+        length = i + 1;
+        storage->setLength(length);
+    }
+
+    // We are currently using a map - check whether we still want to be doing so.
+    // We will continue  to use a sparse map if SparseMode is set, a vector would be too sparse, or if allocation fails.
+    unsigned numValuesInArray = storage->m_numValuesInVector + map->size();
+    if (map->sparseMode() || !isDenseEnoughForVector(length, numValuesInArray) || !increaseVectorLength(exec->globalData(), length)) {
+        map->putEntry(exec, this, i, value, shouldThrow);
+        return;
+    }
+
+    // Reread m_storage after increaseVectorLength, update m_numValuesInVector.
+    storage = arrayStorage();
+    storage->m_numValuesInVector = numValuesInArray;
+
+    // Copy all values from the map into the vector, and delete the map.
+    WriteBarrier<Unknown>* vector = storage->m_vector;
+    SparseArrayValueMap::const_iterator end = map->end();
+    for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
+        vector[it->first].set(globalData, this, it->second.getNonSparseMode());
+    deallocateSparseIndexMap();
+
+    // Store the new property into the vector.
+    WriteBarrier<Unknown>& valueSlot = vector[i];
+    if (!valueSlot)
+        ++storage->m_numValuesInVector;
+    valueSlot.set(globalData, this, value);
+}
+
+void JSObject::putByIndexBeyondVectorLength(ExecState* exec, unsigned i, JSValue value, bool shouldThrow)
+{
+    JSGlobalData& globalData = exec->globalData();
+
+    // i should be a valid array index that is outside of the current vector.
+    ASSERT(i <= MAX_ARRAY_INDEX);
+    
+    switch (structure()->indexingType()) {
+    case NonArray:
+    case Array: {
+        if (indexingShouldBeSparse()) {
+            putByIndexBeyondVectorLengthWithArrayStorage(exec, i, value, shouldThrow, ensureArrayStorageExistsAndEnterDictionaryIndexingMode(globalData));
+            break;
+        }
+        if (!isDenseEnoughForVector(i, 0) || i >= MAX_STORAGE_VECTOR_LENGTH) {
+            putByIndexBeyondVectorLengthWithArrayStorage(exec, i, value, shouldThrow, createArrayStorage(globalData, 0, 0));
+            break;
+        }
+        
+        ArrayStorage* storage = createArrayStorage(globalData, i + 1, getNewVectorLength(0, 0, i + 1));
+        storage->m_vector[i].set(globalData, this, value);
+        storage->m_numValuesInVector = 1;
+        break;
+    }
+
+    case NonArrayWithArrayStorage:
+    case ArrayWithArrayStorage:
+        putByIndexBeyondVectorLengthWithArrayStorage(exec, i, value, shouldThrow, arrayStorage());
+        break;
+        
+    default:
+        ASSERT_NOT_REACHED();
+    }
+}
+
+bool JSObject::putDirectIndexBeyondVectorLengthWithArrayStorage(ExecState* exec, unsigned i, JSValue value, unsigned attributes, PutDirectIndexMode mode, ArrayStorage* storage)
+{
+    JSGlobalData& globalData = exec->globalData();
+
+    // i should be a valid array index that is outside of the current vector.
+    ASSERT(i >= storage->vectorLength() || attributes);
+    ASSERT(i <= MAX_ARRAY_INDEX);
+
+    SparseArrayValueMap* map = storage->m_sparseMap.get();
+
+    // First, handle cases where we don't currently have a sparse map.
+    if (LIKELY(!map)) {
+        // If the array is not extensible, we should have entered dictionary mode, and created the spare map.
+        ASSERT(isExtensible());
+    
+        // Update m_length if necessary.
+        if (i >= storage->length())
+            storage->setLength(i + 1);
+
+        // Check that it is sensible to still be using a vector, and then try to grow the vector.
+        if (LIKELY(
+                !attributes
+                && (isDenseEnoughForVector(i, storage->m_numValuesInVector))
+                && increaseVectorLength(globalData, i + 1))) {
+            // success! - reread m_storage since it has likely been reallocated, and store to the vector.
+            storage = arrayStorage();
+            storage->m_vector[i].set(globalData, this, value);
+            ++storage->m_numValuesInVector;
+            return true;
+        }
+        // We don't want to, or can't use a vector to hold this property - allocate a sparse map & add the value.
+        map = allocateSparseIndexMap(exec->globalData());
+        return map->putDirect(exec, this, i, value, attributes, mode);
+    }
+
+    // Update m_length if necessary.
+    unsigned length = storage->length();
+    if (i >= length) {
+        if (mode != PutDirectIndexLikePutDirect) {
+            // Prohibit growing the array if length is not writable.
+            if (map->lengthIsReadOnly())
+                return reject(exec, mode == PutDirectIndexShouldThrow, StrictModeReadonlyPropertyWriteError);
+            if (!isExtensible())
+                return reject(exec, mode == PutDirectIndexShouldThrow, "Attempting to define property on object that is not extensible.");
+        }
+        length = i + 1;
+        storage->setLength(length);
+    }
+
+    // We are currently using a map - check whether we still want to be doing so.
+    // We will continue  to use a sparse map if SparseMode is set, a vector would be too sparse, or if allocation fails.
+    unsigned numValuesInArray = storage->m_numValuesInVector + map->size();
+    if (map->sparseMode() || attributes || !isDenseEnoughForVector(length, numValuesInArray) || !increaseVectorLength(exec->globalData(), length))
+        return map->putDirect(exec, this, i, value, attributes, mode);
+
+    // Reread m_storage after increaseVectorLength, update m_numValuesInVector.
+    storage = arrayStorage();
+    storage->m_numValuesInVector = numValuesInArray;
+
+    // Copy all values from the map into the vector, and delete the map.
+    WriteBarrier<Unknown>* vector = storage->m_vector;
+    SparseArrayValueMap::const_iterator end = map->end();
+    for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
+        vector[it->first].set(globalData, this, it->second.getNonSparseMode());
+    deallocateSparseIndexMap();
+
+    // Store the new property into the vector.
+    WriteBarrier<Unknown>& valueSlot = vector[i];
+    if (!valueSlot)
+        ++storage->m_numValuesInVector;
+    valueSlot.set(globalData, this, value);
+    return true;
+}
+
+bool JSObject::putDirectIndexBeyondVectorLength(ExecState* exec, unsigned i, JSValue value, unsigned attributes, PutDirectIndexMode mode)
+{
+    JSGlobalData& globalData = exec->globalData();
+
+    // i should be a valid array index that is outside of the current vector.
+    ASSERT(i <= MAX_ARRAY_INDEX);
+    
+    switch (structure()->indexingType()) {
+    case NonArray:
+    case Array: {
+        if (indexingShouldBeSparse() || attributes)
+            return putDirectIndexBeyondVectorLengthWithArrayStorage(exec, i, value, attributes, mode, ensureArrayStorageExistsAndEnterDictionaryIndexingMode(globalData));
+        if (!isDenseEnoughForVector(i, 0) || i >= MAX_STORAGE_VECTOR_LENGTH)
+            return putDirectIndexBeyondVectorLengthWithArrayStorage(exec, i, value, attributes, mode, createArrayStorage(globalData, 0, 0));
+        
+        ArrayStorage* storage = createArrayStorage(globalData, i + 1, getNewVectorLength(0, 0, i + 1));
+        storage->m_vector[i].set(globalData, this, value);
+        storage->m_numValuesInVector = 1;
+        return true;
+    }
+
+    case NonArrayWithArrayStorage:
+    case ArrayWithArrayStorage:
+        return putDirectIndexBeyondVectorLengthWithArrayStorage(exec, i, value, attributes, mode, arrayStorage());
+        
+    default:
+        ASSERT_NOT_REACHED();
+        return false;
+    }
+}
+
+ALWAYS_INLINE unsigned JSObject::getNewVectorLength(unsigned currentVectorLength, unsigned currentLength, unsigned desiredLength)
+{
+    ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);
+
+    unsigned increasedLength;
+    unsigned maxInitLength = std::min(currentLength, 100000U);
+
+    if (desiredLength < maxInitLength)
+        increasedLength = maxInitLength;
+    else if (!currentVectorLength)
+        increasedLength = std::max(desiredLength, lastArraySize);
+    else {
+        // Mathematically equivalent to:
+        //   increasedLength = (newLength * 3 + 1) / 2;
+        // or:
+        //   increasedLength = (unsigned)ceil(newLength * 1.5));
+        // This form is not prone to internal overflow.
+        increasedLength = desiredLength + (desiredLength >> 1) + (desiredLength & 1);
+    }
+
+    ASSERT(increasedLength >= desiredLength);
+
+    lastArraySize = std::min(increasedLength, FIRST_VECTOR_GROW);
+
+    return std::min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
+}
+
+ALWAYS_INLINE unsigned JSObject::getNewVectorLength(unsigned desiredLength)
+{
+    unsigned vectorLength;
+    unsigned length;
+    
+    switch (structure()->indexingType()) {
+    case NonArray:
+    case Array:
+        vectorLength = 0;
+        length = 0;
+        break;
+    case NonArrayWithArrayStorage:
+    case ArrayWithArrayStorage:
+        vectorLength = m_butterfly->arrayStorage()->vectorLength();
+        length = m_butterfly->arrayStorage()->length();
+        break;
+    default:
+        CRASH();
+        return 0;
+    }
+    return getNewVectorLength(vectorLength, length, desiredLength);
+}
+
+bool JSObject::increaseVectorLength(JSGlobalData& globalData, unsigned newLength)
+{
+    // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
+    // to the vector. Callers have to account for that, because they can do it more efficiently.
+    if (newLength > MAX_STORAGE_VECTOR_LENGTH)
+        return false;
+
+    ArrayStorage* storage = arrayStorage();
+
+    unsigned indexBias = storage->m_indexBias;
+    unsigned vectorLength = storage->vectorLength();
+    ASSERT(newLength > vectorLength);
+    unsigned newVectorLength = getNewVectorLength(newLength);
+
+    // Fast case - there is no precapacity. In these cases a realloc makes sense.
+    if (LIKELY(!indexBias)) {
+        Butterfly* newButterfly = storage->butterfly()->growArrayRight(globalData, structure(), structure()->outOfLineCapacity(), true, ArrayStorage::sizeFor(vectorLength), ArrayStorage::sizeFor(newVectorLength));
+        if (!newButterfly)
+            return false;
+        m_butterfly = newButterfly;
+        newButterfly->arrayStorage()->setVectorLength(newVectorLength);
+        return true;
+    }
+    
+    // Remove some, but not all of the precapacity. Atomic decay, & capped to not overflow array length.
+    unsigned newIndexBias = std::min(indexBias >> 1, MAX_STORAGE_VECTOR_LENGTH - newVectorLength);
+    Butterfly* newButterfly = storage->butterfly()->resizeArray(
+        globalData,
+        structure()->outOfLineCapacity(), true, ArrayStorage::sizeFor(vectorLength),
+        newIndexBias, true, ArrayStorage::sizeFor(newVectorLength));
+    if (!newButterfly)
+        return false;
+    
+    m_butterfly = newButterfly;
+    newButterfly->arrayStorage()->setVectorLength(newVectorLength);
+    newButterfly->arrayStorage()->m_indexBias = newIndexBias;
+    return true;
+}
+
+#if CHECK_ARRAY_CONSISTENCY
+void JSObject::checkIndexingConsistency(ConsistencyCheckType type)
+{
+    ArrayStorage* storage = arrayStorageOrNull();
+    if (!storage)
+        return;
+
+    ASSERT(!storage->m_inCompactInitialization);
+
+    ASSERT(storage);
+    if (type == SortConsistencyCheck)
+        ASSERT(!storage->m_sparseMap);
+
+    unsigned numValuesInVector = 0;
+    for (unsigned i = 0; i < storage->vectorLength(); ++i) {
+        if (JSValue value = storage->m_vector[i].get()) {
+            ASSERT(i < storage->length());
+            if (type != DestructorConsistencyCheck)
+                value.isUndefined(); // Likely to crash if the object was deallocated.
+            ++numValuesInVector;
+        } else {
+            if (type == SortConsistencyCheck)
+                ASSERT(i >= storage->m_numValuesInVector);
+        }
+    }
+    ASSERT(numValuesInVector == storage->m_numValuesInVector);
+    ASSERT(numValuesInVector <= storage->length());
+
+    if (m_sparseValueMap) {
+        SparseArrayValueMap::const_iterator end = m_sparseValueMap->end();
+        for (SparseArrayValueMap::const_iterator it = m_sparseValueMap->begin(); it != end; ++it) {
+            unsigned index = it->first;
+            ASSERT(index < storage->length());
+            ASSERT(index >= storage->vectorLength());
+            ASSERT(index <= MAX_ARRAY_INDEX);
+            ASSERT(it->second);
+            if (type != DestructorConsistencyCheck)
+                it->second.getNonSparseMode().isUndefined(); // Likely to crash if the object was deallocated.
+        }
+    }
+}
+#endif // CHECK_ARRAY_CONSISTENCY
+
+Butterfly* JSObject::growOutOfLineStorage(JSGlobalData& globalData, size_t oldSize, size_t newSize)
 {
     ASSERT(newSize > oldSize);
 
-    // It's important that this function not rely on structure(), since
-    // we might be in the middle of a transition.
-    
-    PropertyStorage oldPropertyStorage = m_outOfLineStorage.get();
-    PropertyStorage newPropertyStorage = 0;
-
-    // We have this extra temp here to slake GCC's thirst for the blood of those who dereference type-punned pointers.
-    void* temp = newPropertyStorage;
-    if (!globalData.heap.tryAllocateStorage(sizeof(WriteBarrierBase<Unknown>) * newSize, &temp))
-        CRASH();
-    newPropertyStorage = static_cast<PropertyStorage>(temp) + newSize + 1;
-    
-    memcpy(newPropertyStorage - oldSize - 1, oldPropertyStorage - oldSize - 1, sizeof(WriteBarrierBase<Unknown>) * oldSize);
-
-    ASSERT(newPropertyStorage);
-    return newPropertyStorage;
+    // It's important that this function not rely on structure(), for the property
+    // capacity, since we might have already mutated the structure in-place.
+    
+    return m_butterfly->growPropertyStorage(globalData, structure(), oldSize, newSize);
 }
 
@@ -631 +1469 @@
     JSCell* cell = 0;
     PropertyOffset offset = object->structure()->get(exec->globalData(), propertyName, attributes, cell);
-    if (offset == invalidOffset)
+    if (isValidOffset(offset)) {
+        descriptor.setDescriptor(object->getDirectOffset(offset), attributes);
+        return true;
+    }
+    
+    unsigned i = propertyName.asIndex();
+    if (i == PropertyName::NotAnIndex)
         return false;
-    descriptor.setDescriptor(object->getDirectOffset(offset), attributes);
-    return true;
+    
+    switch (object->structure()->indexingType()) {
+    case NonArray:
+    case Array:
+        return false;
+        
+    case NonArrayWithArrayStorage:
+    case ArrayWithArrayStorage: {
+        ArrayStorage* storage = object->m_butterfly->arrayStorage();
+        if (i >= storage->length())
+            return false;
+        if (i < storage->vectorLength()) {
+            WriteBarrier<Unknown>& value = storage->m_vector[i];
+            if (!value)
+                return false;
+            descriptor.setDescriptor(value.get(), 0);
+            return true;
+        }
+        if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
+            SparseArrayValueMap::iterator it = map->find(i);
+            if (it == map->notFound())
+                return false;
+            it->second.get(descriptor);
+            return true;
+        }
+        return false;
+    }
+        
+    default:
+        ASSERT_NOT_REACHED();
+        return false;
+    }
 }
 
@@ -659 +1533 @@
             if (oldDescriptor.setterPresent())
                 accessor->setSetter(exec->globalData(), oldDescriptor.setterObject());
-            target->putDirectAccessor(exec->globalData(), propertyName, accessor, attributes | Accessor);
+            target->putDirectAccessor(exec, propertyName, accessor, attributes | Accessor);
             return true;
         }
@@ -684 +1558 @@
         accessor->setSetter(exec->globalData(), oldDescriptor.setterObject());
 
-    target->putDirectAccessor(exec->globalData(), propertyName, accessor, attributes | Accessor);
+    target->putDirectAccessor(exec, propertyName, accessor, attributes | Accessor);
     return true;
+}
+
+void JSObject::putDirectMayBeIndex(ExecState* exec, PropertyName propertyName, JSValue value)
+{
+    unsigned asIndex = propertyName.asIndex();
+    if (asIndex == PropertyName::NotAnIndex)
+        putDirect(exec->globalData(), propertyName, value);
+    else
+        putDirectIndex(exec, asIndex, value);
 }
 
@@ -705 +1588 @@
 };
 
-bool JSObject::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor, bool throwException)
+bool JSObject::defineOwnNonIndexProperty(ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor, bool throwException)
 {
     // Track on the globaldata that we're in define property.
@@ -712 +1595 @@
     // DontDelete) properties to be deleted. For now, we can use this flag to make this work.
     DefineOwnPropertyScope scope(exec);
-
+    
     // If we have a new property we can just put it on normally
     PropertyDescriptor current;
-    if (!object->methodTable()->getOwnPropertyDescriptor(object, exec, propertyName, current)) {
+    if (!methodTable()->getOwnPropertyDescriptor(this, exec, propertyName, current)) {
         // unless extensions are prevented!
-        if (!object->isExtensible()) {
+        if (!isExtensible()) {
             if (throwException)
                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to define property on object that is not extensible.")));
@@ -724 +1607 @@
         PropertyDescriptor oldDescriptor;
         oldDescriptor.setValue(jsUndefined());
-        return putDescriptor(exec, object, propertyName, descriptor, descriptor.attributes(), oldDescriptor);
+        return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributes(), oldDescriptor);
     }
 
@@ -750 +1633 @@
     if (descriptor.isGenericDescriptor()) {
         if (!current.attributesEqual(descriptor)) {
-            object->methodTable()->deleteProperty(object, exec, propertyName);
-            return putDescriptor(exec, object, propertyName, descriptor, descriptor.attributesOverridingCurrent(current), current);
+            methodTable()->deleteProperty(this, exec, propertyName);
+            return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributesOverridingCurrent(current), current);
         }
         return true;
@@ -763 +1646 @@
             return false;
         }
-        object->methodTable()->deleteProperty(object, exec, propertyName);
-        return putDescriptor(exec, object, propertyName, descriptor, descriptor.attributesOverridingCurrent(current), current);
+        methodTable()->deleteProperty(this, exec, propertyName);
+        return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributesOverridingCurrent(current), current);
     }
 
@@ -785 +1668 @@
         if (current.attributesEqual(descriptor) && !descriptor.value())
             return true;
-        object->methodTable()->deleteProperty(object, exec, propertyName);
-        return putDescriptor(exec, object, propertyName, descriptor, descriptor.attributesOverridingCurrent(current), current);
+        methodTable()->deleteProperty(this, exec, propertyName);
+        return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributesOverridingCurrent(current), current);
     }
 
@@ -803 +1686 @@
         }
     }
-    JSValue accessor = object->getDirect(exec->globalData(), propertyName);
+    JSValue accessor = getDirect(exec->globalData(), propertyName);
     if (!accessor)
         return false;
@@ -813 +1696 @@
     if (current.attributesEqual(descriptor))
         return true;
-    object->methodTable()->deleteProperty(object, exec, propertyName);
+    methodTable()->deleteProperty(this, exec, propertyName);
     unsigned attrs = descriptor.attributesOverridingCurrent(current);
-    object->putDirectAccessor(exec->globalData(), propertyName, getterSetter, attrs | Accessor);
+    putDirectAccessor(exec, propertyName, getterSetter, attrs | Accessor);
     return true;
 }
 
+bool JSObject::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor, bool throwException)
+{
+    // If it's an array index, then use the indexed property storage.
+    unsigned index = propertyName.asIndex();
+    if (index != PropertyName::NotAnIndex) {
+        // 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.
+        // d. Reject if succeeded is false.
+        // e. If index >= oldLen
+        // e.i. Set oldLenDesc.[[Value]] to index + 1.
+        // 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.
+        // f. Return true.
+        return object->defineOwnIndexedProperty(exec, index, descriptor, throwException);
+    }
+    
+    return object->defineOwnNonIndexProperty(exec, propertyName, descriptor, throwException);
+}
+
+bool JSObject::getOwnPropertySlotSlow(ExecState* exec, PropertyName propertyName, PropertySlot& slot)
+{
+    unsigned i = propertyName.asIndex();
+    if (i != PropertyName::NotAnIndex)
+        return getOwnPropertySlotByIndex(this, exec, i, slot);
+    return false;
+}
+
 JSObject* throwTypeError(ExecState* exec, const String& message)
 {

trunk/Source/JavaScriptCore/runtime/JSObject.h

@@ -2 +2 @@
  *  Copyright (C) 1999-2001 Harri Porten ([email protected])
  *  Copyright (C) 2001 Peter Kelly ([email protected])
- *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
+ *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2012 Apple Inc. All rights reserved.
  *
  *  This library is free software; you can redistribute it and/or
@@ -25 +25 @@
 
 #include "ArgList.h"
+#include "ArrayConventions.h"
+#include "ArrayStorage.h"
+#include "Butterfly.h"
 #include "ClassInfo.h"
 #include "CommonIdentifiers.h"
@@ -30 +33 @@
 #include "JSCell.h"
 #include "PropertySlot.h"
+#include "PropertyStorage.h"
+#include "PutDirectIndexMode.h"
 #include "PutPropertySlot.h"
 
-#include "StorageBarrier.h"
 #include "Structure.h"
 #include "JSGlobalData.h"
 #include "JSString.h"
+#include "SparseArrayValueMap.h"
 #include <wtf/StdLibExtras.h>
 
@@ -80 +85 @@
     };
 
+    COMPILE_ASSERT(None < FirstInternalAttribute, None_is_below_FirstInternalAttribute);
+    COMPILE_ASSERT(ReadOnly < FirstInternalAttribute, ReadOnly_is_below_FirstInternalAttribute);
+    COMPILE_ASSERT(DontEnum < FirstInternalAttribute, DontEnum_is_below_FirstInternalAttribute);
+    COMPILE_ASSERT(DontDelete < FirstInternalAttribute, DontDelete_is_below_FirstInternalAttribute);
+    COMPILE_ASSERT(Function < FirstInternalAttribute, Function_is_below_FirstInternalAttribute);
+    COMPILE_ASSERT(Accessor < FirstInternalAttribute, Accessor_is_below_FirstInternalAttribute);
+
     class JSFinalObject;
 
@@ -97 +109 @@
     public:
         typedef JSCell Base;
-
+        
         JS_EXPORT_PRIVATE static void visitChildren(JSCell*, SlotVisitor&);
 
@@ -121 +133 @@
         bool allowsAccessFrom(ExecState*);
 
+        unsigned getArrayLength() const
+        {
+            switch (structure()->indexingType()) {
+            case NonArray:
+            case Array:
+                return 0;
+            case NonArrayWithArrayStorage:
+            case ArrayWithArrayStorage:
+                return m_butterfly->arrayStorage()->length();
+            default:
+                ASSERT_NOT_REACHED();
+                return 0;
+            }
+        }
+        
+        unsigned getVectorLength()
+        {
+            switch (structure()->indexingType()) {
+            case NonArray:
+            case Array:
+                return 0;
+            case NonArrayWithArrayStorage:
+            case ArrayWithArrayStorage:
+                return m_butterfly->arrayStorage()->vectorLength();
+            default:
+                ASSERT_NOT_REACHED();
+                return 0;
+            }
+        }
+        
         JS_EXPORT_PRIVATE static void put(JSCell*, ExecState*, PropertyName, JSValue, PutPropertySlot&);
         JS_EXPORT_PRIVATE static void putByIndex(JSCell*, ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
+        
+        // This is similar to the putDirect* methods:
+        //  - the prototype chain is not consulted
+        //  - accessors are not called.
+        //  - it will ignore extensibility and read-only properties if PutDirectIndexLikePutDirect is passed as the mode (the default).
+        // This method creates a property with attributes writable, enumerable and configurable all set to true.
+        bool putDirectIndex(ExecState* exec, unsigned propertyName, JSValue value, unsigned attributes, PutDirectIndexMode mode)
+        {
+            if (!attributes && canSetIndexQuickly(propertyName)) {
+                setIndexQuickly(exec->globalData(), propertyName, value);
+                return true;
+            }
+            return putDirectIndexBeyondVectorLength(exec, propertyName, value, attributes, mode);
+        }
+        bool putDirectIndex(ExecState* exec, unsigned propertyName, JSValue value)
+        {
+            return putDirectIndex(exec, propertyName, value, 0, PutDirectIndexLikePutDirect);
+        }
+
+        // A non-throwing version of putDirect and putDirectIndex.
+        void putDirectMayBeIndex(ExecState*, PropertyName, JSValue);
+        
+        bool canGetIndexQuickly(unsigned i)
+        {
+            switch (structure()->indexingType()) {
+            case NonArray:
+            case Array:
+                return false;
+            case NonArrayWithArrayStorage:
+            case ArrayWithArrayStorage:
+                return i < m_butterfly->arrayStorage()->vectorLength() && m_butterfly->arrayStorage()->m_vector[i];
+            default:
+                ASSERT_NOT_REACHED();
+                return false;
+            }
+        }
+        
+        JSValue getIndexQuickly(unsigned i)
+        {
+            switch (structure()->indexingType()) {
+            case NonArrayWithArrayStorage:
+            case ArrayWithArrayStorage:
+                return m_butterfly->arrayStorage()->m_vector[i].get();
+            default:
+                ASSERT_NOT_REACHED();
+                return JSValue();
+            }
+        }
+        
+        bool canSetIndexQuickly(unsigned i)
+        {
+            switch (structure()->indexingType()) {
+            case NonArray:
+            case Array:
+                return false;
+            case NonArrayWithArrayStorage:
+            case ArrayWithArrayStorage:
+                return i < m_butterfly->arrayStorage()->vectorLength();
+            default:
+                ASSERT_NOT_REACHED();
+                return false;
+            }
+        }
+        
+        void setIndexQuickly(JSGlobalData& globalData, unsigned i, JSValue v)
+        {
+            switch (structure()->indexingType()) {
+            case NonArrayWithArrayStorage:
+            case ArrayWithArrayStorage: {
+                WriteBarrier<Unknown>& x = m_butterfly->arrayStorage()->m_vector[i];
+                if (!x) {
+                    ArrayStorage* storage = m_butterfly->arrayStorage();
+                    ++storage->m_numValuesInVector;
+                    if (i >= storage->length())
+                        storage->setLength(i + 1);
+                }
+                x.set(globalData, this, v);
+                break;
+            }
+            default:
+                ASSERT_NOT_REACHED();
+            }
+        }
+        
+        void initializeIndex(JSGlobalData& globalData, unsigned i, JSValue v)
+        {
+            switch (structure()->indexingType()) {
+            case NonArrayWithArrayStorage:
+            case ArrayWithArrayStorage: {
+                ArrayStorage* storage = m_butterfly->arrayStorage();
+#if CHECK_ARRAY_CONSISTENCY
+                ASSERT(storage->m_inCompactInitialization);
+                // Check that we are initializing the next index in sequence.
+                ASSERT(i == storage->m_initializationIndex);
+                // tryCreateUninitialized set m_numValuesInVector to the initialLength,
+                // check we do not try to initialize more than this number of properties.
+                ASSERT(storage->m_initializationIndex < storage->m_numValuesInVector);
+                storage->m_initializationIndex++;
+#endif
+                ASSERT(i < storage->length());
+                ASSERT(i < storage->m_numValuesInVector);
+                storage->m_vector[i].set(globalData, this, v);
+                break;
+            }
+            default:
+                ASSERT_NOT_REACHED();
+            }
+        }
+        
+        void completeInitialization(unsigned newLength)
+        {
+            switch (structure()->indexingType()) {
+            case NonArrayWithArrayStorage:
+            case ArrayWithArrayStorage: {
+                ArrayStorage* storage = m_butterfly->arrayStorage();
+                // Check that we have initialized as meny properties as we think we have.
+                UNUSED_PARAM(storage);
+                ASSERT_UNUSED(newLength, newLength == storage->length());
+#if CHECK_ARRAY_CONSISTENCY
+                // Check that the number of propreties initialized matches the initialLength.
+                ASSERT(storage->m_initializationIndex == m_storage->m_numValuesInVector);
+                ASSERT(storage->m_inCompactInitialization);
+                storage->m_inCompactInitialization = false;
+#endif
+                break;
+            }
+            default:
+                ASSERT_NOT_REACHED();
+            }
+        }
+        
+        bool inSparseIndexingMode()
+        {
+            switch (structure()->indexingType()) {
+            case NonArray:
+            case Array:
+                return false;
+            case NonArrayWithArrayStorage:
+            case ArrayWithArrayStorage:
+                return m_butterfly->arrayStorage()->inSparseMode();
+            default:
+                ASSERT_NOT_REACHED();
+                return false;
+            }
+        }
+        
+        void enterDictionaryIndexingMode(JSGlobalData&);
 
         // putDirect is effectively an unchecked vesion of 'defineOwnProperty':
@@ -128 +317 @@
         //  - accessors are not called.
         //  - attributes will be respected (after the call the property will exist with the given attributes)
+        //  - the property name is assumed to not be an index.
         JS_EXPORT_PRIVATE static void putDirectVirtual(JSObject*, ExecState*, PropertyName, JSValue, unsigned attributes);
         void putDirect(JSGlobalData&, PropertyName, JSValue, unsigned attributes = 0);
         void putDirect(JSGlobalData&, PropertyName, JSValue, PutPropertySlot&);
         void putDirectWithoutTransition(JSGlobalData&, PropertyName, JSValue, unsigned attributes = 0);
-        void putDirectAccessor(JSGlobalData&, PropertyName, JSValue, unsigned attributes);
+        void putDirectAccessor(ExecState*, PropertyName, JSValue, unsigned attributes);
 
         bool propertyIsEnumerable(ExecState*, const Identifier& propertyName) const;
@@ -148 +338 @@
 
         JS_EXPORT_PRIVATE static void getOwnPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
+        JS_EXPORT_PRIVATE static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
         JS_EXPORT_PRIVATE static void getPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
 
@@ -204 +395 @@
         }
         
-        ConstPropertyStorage outOfLineStorage() const { return m_outOfLineStorage.get(); }
-        PropertyStorage outOfLineStorage() { return m_outOfLineStorage.get(); }
+        const Butterfly* butterfly() const { return m_butterfly; }
+        Butterfly* butterfly() { return m_butterfly; }
+        
+        ConstPropertyStorage outOfLineStorage() const { return m_butterfly->propertyStorage(); }
+        PropertyStorage outOfLineStorage() { return m_butterfly->propertyStorage(); }
 
         const WriteBarrierBase<Unknown>* locationForOffset(PropertyOffset offset) const
@@ -228 +422 @@
                 result = offsetInInlineStorage;
             else
-                result = outOfLineStorage() - location + (inlineStorageCapacity - 2);
+                result = outOfLineStorage() - location + (inlineStorageCapacity - 1);
             validateOffset(result, structure()->typeInfo().type());
             return result;
@@ -266 +460 @@
         bool isFrozen(JSGlobalData& globalData) { return structure()->isFrozen(globalData); }
         bool isExtensible() { return structure()->isExtensible(); }
+        bool indexingShouldBeSparse()
+        {
+            return !isExtensible()
+                || structure()->typeInfo().interceptsGetOwnPropertySlotByIndexEvenWhenLengthIsNotZero();
+        }
 
         bool staticFunctionsReified() { return structure()->staticFunctionsReified(); }
         void reifyStaticFunctionsForDelete(ExecState* exec);
 
-        JS_EXPORT_PRIVATE PropertyStorage growOutOfLineStorage(JSGlobalData&, size_t oldSize, size_t newSize);
-        void setOutOfLineStorage(JSGlobalData&, PropertyStorage, Structure*);
+        JS_EXPORT_PRIVATE Butterfly* growOutOfLineStorage(JSGlobalData&, size_t oldSize, size_t newSize);
+        void setButterfly(JSGlobalData&, Butterfly*, Structure*);
+        void setButterflyWithoutChangingStructure(Butterfly*); // You probably don't want to call this.
         
         void setStructureAndReallocateStorageIfNecessary(JSGlobalData&, unsigned oldCapacity, Structure*);
         void setStructureAndReallocateStorageIfNecessary(JSGlobalData&, Structure*);
-
-        void* addressOfOutOfLineStorage()
-        {
-            return &m_outOfLineStorage;
-        }
 
         void flattenDictionaryObject(JSGlobalData& globalData)
@@ -294 +489 @@
         
         static size_t offsetOfInlineStorage();
-        static size_t offsetOfOutOfLineStorage();
+        
+        static ptrdiff_t butterflyOffset()
+        {
+            return OBJECT_OFFSETOF(JSObject, m_butterfly);
+        }
+        
+        void* butterflyAddress()
+        {
+            return &m_butterfly;
+        }
 
         static JS_EXPORTDATA const ClassInfo s_info;
@@ -317 +521 @@
         // To instantiate objects you likely want JSFinalObject, below.
         // To create derived types you likely want JSNonFinalObject, below.
-        JSObject(JSGlobalData&, Structure*);
+        JSObject(JSGlobalData&, Structure*, Butterfly* = 0);
         
         void resetInheritorID(JSGlobalData& globalData)
@@ -324 +528 @@
         }
         
-        void visitOutOfLineStorage(SlotVisitor&, PropertyStorage, size_t storageSize);
+        void visitButterfly(SlotVisitor&, Butterfly*, size_t storageSize);
+
+        // Call this if you know that the object is in a mode where it has array
+        // storage. This will assert otherwise.
+        ArrayStorage* arrayStorage()
+        {
+            ASSERT(structure()->indexingType() | HasArrayStorage);
+            return m_butterfly->arrayStorage();
+        }
+        
+        // Call this if you want to predicate some actions on whether or not the
+        // object is in a mode where it has array storage.
+        ArrayStorage* arrayStorageOrNull()
+        {
+            switch (structure()->indexingType()) {
+            case ArrayWithArrayStorage:
+            case NonArrayWithArrayStorage:
+                return m_butterfly->arrayStorage();
+                
+            default:
+                return 0;
+            }
+        }
+
+        // Ensure that the object is in a mode where it has array storage. Use
+        // this if you're about to perform actions that would have required the
+        // object to be converted to have array storage, if it didn't have it
+        // already.
+        ArrayStorage* ensureArrayStorage(JSGlobalData& globalData)
+        {
+            switch (structure()->indexingType()) {
+            case ArrayWithArrayStorage:
+            case NonArrayWithArrayStorage:
+                return m_butterfly->arrayStorage();
+                
+            case NonArray:
+            case Array:
+                return createInitialArrayStorage(globalData);
+                
+            default:
+                ASSERT_NOT_REACHED();
+                return 0;
+            }
+        }
+        
+        ArrayStorage* createArrayStorage(JSGlobalData&, unsigned length, unsigned vectorLength);
+        ArrayStorage* createInitialArrayStorage(JSGlobalData&);
+        
+        ArrayStorage* ensureArrayStorageExistsAndEnterDictionaryIndexingMode(JSGlobalData&);
+        
+        bool defineOwnNonIndexProperty(ExecState*, PropertyName, PropertyDescriptor&, bool throwException);
+
+        enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck };
+#if !CHECK_ARRAY_CONSISTENCY
+        void checkIndexingConsistency(ConsistencyCheckType = NormalConsistencyCheck) { }
+#else
+        void checkIndexingConsistency(ConsistencyCheckType = NormalConsistencyCheck);
+#endif
+        
+        void putByIndexBeyondVectorLengthWithArrayStorage(ExecState*, unsigned propertyName, JSValue, bool shouldThrow, ArrayStorage*);
+
+        bool increaseVectorLength(JSGlobalData&, unsigned newLength);
+        void deallocateSparseIndexMap();
+        bool defineOwnIndexedProperty(ExecState*, unsigned, PropertyDescriptor&, bool throwException);
+        SparseArrayValueMap* allocateSparseIndexMap(JSGlobalData&);
 
     private:
@@ -337 +605 @@
         void isString();
         
+        ArrayStorage* enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(JSGlobalData&, ArrayStorage*);
+        
         template<PutMode>
         bool putDirectInternal(JSGlobalData&, PropertyName, JSValue, unsigned attr, PutPropertySlot&, JSCell*);
 
         bool inlineGetOwnPropertySlot(ExecState*, PropertyName, PropertySlot&);
-        JS_EXPORT_PRIVATE void fillGetterPropertySlot(PropertySlot&, WriteBarrierBase<Unknown>* location);
+        JS_EXPORT_PRIVATE void fillGetterPropertySlot(PropertySlot&, PropertyOffset);
 
         const HashEntry* findPropertyHashEntry(ExecState*, PropertyName) const;
         Structure* createInheritorID(JSGlobalData&);
-
-        StorageBarrier m_outOfLineStorage;
+        
+        void putIndexedDescriptor(ExecState*, SparseArrayEntry*, PropertyDescriptor&, PropertyDescriptor& old);
+        
+        void putByIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
+        bool putDirectIndexBeyondVectorLengthWithArrayStorage(ExecState*, unsigned propertyName, JSValue, unsigned attributes, PutDirectIndexMode, ArrayStorage*);
+        JS_EXPORT_PRIVATE bool putDirectIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, unsigned attributes, PutDirectIndexMode);
+        
+        unsigned getNewVectorLength(unsigned currentVectorLength, unsigned currentLength, unsigned desiredLength);
+        unsigned getNewVectorLength(unsigned desiredLength);
+
+        JS_EXPORT_PRIVATE bool getOwnPropertySlotSlow(ExecState*, PropertyName, PropertySlot&);
+        
+    protected:
+        Butterfly* m_butterfly;
     };
 
@@ -370 +652 @@
 
     protected:
-        explicit JSNonFinalObject(JSGlobalData& globalData, Structure* structure)
-            : JSObject(globalData, structure)
+        explicit JSNonFinalObject(JSGlobalData& globalData, Structure* structure, Butterfly* butterfly = 0)
+            : JSObject(globalData, structure, butterfly)
         {
         }
@@ -454 +736 @@
 }
 
-inline size_t JSObject::offsetOfOutOfLineStorage()
-{
-    return OBJECT_OFFSETOF(JSObject, m_outOfLineStorage);
-}
-
 inline bool JSObject::isGlobalObject() const
 {
@@ -489 +766 @@
 }
 
-inline void JSObject::setOutOfLineStorage(JSGlobalData& globalData, PropertyStorage storage, Structure* structure)
+inline void JSObject::setButterfly(JSGlobalData& globalData, Butterfly* butterfly, Structure* structure)
 {
     ASSERT(structure);
-    if (!storage) {
-        ASSERT(!structure->outOfLineCapacity());
-        ASSERT(!structure->outOfLineSize());
-    } else {
-        ASSERT(structure->outOfLineCapacity());
-        ASSERT(structure->outOfLineSize());
-    }
+    ASSERT(!butterfly == (!structure->outOfLineCapacity() && !hasIndexingHeader(structure->indexingType())));
     setStructure(globalData, structure);
-    m_outOfLineStorage.set(globalData, this, storage);
+    m_butterfly = butterfly;
+}
+
+inline void JSObject::setButterflyWithoutChangingStructure(Butterfly* butterfly)
+{
+    m_butterfly = butterfly;
 }
 
@@ -538 +814 @@
 }
 
-inline JSObject::JSObject(JSGlobalData& globalData, Structure* structure)
+inline JSObject::JSObject(JSGlobalData& globalData, Structure* structure, Butterfly* butterfly)
     : JSCell(globalData, structure)
-    , m_outOfLineStorage(globalData, this, 0)
+    , m_butterfly(butterfly)
 {
 }
@@ -588 +864 @@
 ALWAYS_INLINE bool JSObject::inlineGetOwnPropertySlot(ExecState* exec, PropertyName propertyName, PropertySlot& slot)
 {
-    if (WriteBarrierBase<Unknown>* location = getDirectLocation(exec->globalData(), propertyName)) {
-        if (structure()->hasGetterSetterProperties() && location->isGetterSetter())
-            fillGetterPropertySlot(slot, location);
+    PropertyOffset offset = structure()->get(exec->globalData(), propertyName);
+    if (LIKELY(isValidOffset(offset))) {
+        JSValue value = getDirectOffset(offset);
+        if (structure()->hasGetterSetterProperties() && value.isGetterSetter())
+            fillGetterPropertySlot(slot, offset);
         else
-            slot.setValue(this, location->get(), offsetForLocation(location));
+            slot.setValue(this, value, offset);
         return true;
     }
 
-    return false;
+    return getOwnPropertySlotSlow(exec, propertyName, slot);
 }
 
@@ -682 +960 @@
     ASSERT(value.isGetterSetter() == !!(attributes & Accessor));
     ASSERT(!Heap::heap(value) || Heap::heap(value) == Heap::heap(this));
+    ASSERT(propertyName.asIndex() == PropertyName::NotAnIndex);
 
     if (structure()->isDictionary()) {
@@ -710 +989 @@
             return false;
 
-        PropertyStorage newStorage = outOfLineStorage();
+        Butterfly* newButterfly = m_butterfly;
         if (structure()->putWillGrowOutOfLineStorage())
-            newStorage = growOutOfLineStorage(globalData, structure()->outOfLineCapacity(), structure()->suggestedNewOutOfLineStorageCapacity());
+            newButterfly = growOutOfLineStorage(globalData, structure()->outOfLineCapacity(), structure()->suggestedNewOutOfLineStorageCapacity());
         offset = structure()->addPropertyWithoutTransition(globalData, propertyName, attributes, specificFunction);
-        setOutOfLineStorage(globalData, newStorage, structure());
+        setButterfly(globalData, newButterfly, structure());
 
         validateOffset(offset);
@@ -728 +1007 @@
     size_t currentCapacity = structure()->outOfLineCapacity();
     if (Structure* structure = Structure::addPropertyTransitionToExistingStructure(this->structure(), propertyName, attributes, specificFunction, offset)) {
-        PropertyStorage newStorage = outOfLineStorage(); 
+        Butterfly* newButterfly = m_butterfly;
         if (currentCapacity != structure->outOfLineCapacity())
-            newStorage = growOutOfLineStorage(globalData, currentCapacity, structure->outOfLineCapacity());
+            newButterfly = growOutOfLineStorage(globalData, currentCapacity, structure->outOfLineCapacity());
 
         validateOffset(offset);
         ASSERT(structure->isValidOffset(offset));
-        setOutOfLineStorage(globalData, newStorage, structure);
+        setButterfly(globalData, newButterfly, structure);
         putDirectOffset(globalData, offset, value);
         // This is a new property; transitions with specific values are not currently cachable,
@@ -801 +1080 @@
     }
     
-    PropertyStorage newStorage = growOutOfLineStorage(
+    Butterfly* newButterfly = growOutOfLineStorage(
         globalData, oldCapacity, newStructure->outOfLineCapacity());
-    setOutOfLineStorage(globalData, newStorage, newStructure);
+    setButterfly(globalData, newButterfly, newStructure);
 }
 
@@ -837 +1116 @@
 {
     ASSERT(!value.isGetterSetter() && !(attributes & Accessor));
-    PropertyStorage newStorage = outOfLineStorage();
+    Butterfly* newButterfly = m_butterfly;
     if (structure()->putWillGrowOutOfLineStorage())
-        newStorage = growOutOfLineStorage(globalData, structure()->outOfLineCapacity(), structure()->suggestedNewOutOfLineStorageCapacity());
+        newButterfly = growOutOfLineStorage(globalData, structure()->outOfLineCapacity(), structure()->suggestedNewOutOfLineStorageCapacity());
     PropertyOffset offset = structure()->addPropertyWithoutTransition(globalData, propertyName, attributes, getCallableObject(value));
-    setOutOfLineStorage(globalData, newStorage, structure());
+    setButterfly(globalData, newButterfly, structure());
     putDirectOffset(globalData, offset, value);
 }
@@ -933 +1212 @@
 }
 
+inline size_t offsetInButterfly(PropertyOffset offset)
+{
+    return offsetInOutOfLineStorage(offset) + Butterfly::indexOfPropertyStorage();
+}
+
 // This is a helper for patching code where you want to emit a load or store and
 // the base is:
@@ -940 +1224 @@
 {
     if (isOutOfLineOffset(offset))
-        return sizeof(EncodedJSValue) * offsetInOutOfLineStorage(offset);
-    return JSObject::offsetOfInlineStorage() - JSObject::offsetOfOutOfLineStorage() + sizeof(EncodedJSValue) * offsetInInlineStorage(offset);
+        return sizeof(EncodedJSValue) * offsetInButterfly(offset);
+    return JSObject::offsetOfInlineStorage() - JSObject::butterflyOffset() + sizeof(EncodedJSValue) * offsetInInlineStorage(offset);
 }
 
@@ -947 +1231 @@
 {
     if (isOutOfLineOffset(offset))
-        return offsetInOutOfLineStorage(offset);
+        return offsetInOutOfLineStorage(offset) + Butterfly::indexOfPropertyStorage();
     ASSERT(!(JSObject::offsetOfInlineStorage() % sizeof(EncodedJSValue)));
     return JSObject::offsetOfInlineStorage() / sizeof(EncodedJSValue) + offsetInInlineStorage(offset);
@@ -955 +1239 @@
 {
     if (isOutOfLineOffset(offset))
-        return offsetInOutOfLineStorage(offset) * sizeof(EncodedJSValue);
+        return offsetInOutOfLineStorage(offset) * sizeof(EncodedJSValue) + Butterfly::offsetOfPropertyStorage();
     return JSObject::offsetOfInlineStorage() + offsetInInlineStorage(offset) * sizeof(EncodedJSValue);
 }

trunk/Source/JavaScriptCore/runtime/JSPropertyNameIterator.cpp

@@ -68 +68 @@
         return jsPropertyNameIterator;
     
+    if (hasIndexingHeader(o->structure()->indexingType()))
+        return jsPropertyNameIterator;
+    
     size_t count = normalizePrototypeChain(exec, o);
     StructureChain* structureChain = o->structure()->prototypeChain(exec);

trunk/Source/JavaScriptCore/runtime/JSSymbolTableObject.cpp

@@ -57 +57 @@
 }
 
-void JSSymbolTableObject::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
+void JSSymbolTableObject::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
 {
     JSSymbolTableObject* thisObject = jsCast<JSSymbolTableObject*>(object);
@@ -66 +66 @@
     }
     
-    JSObject::getOwnPropertyNames(thisObject, exec, propertyNames, mode);
+    JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode);
 }
 

trunk/Source/JavaScriptCore/runtime/JSSymbolTableObject.h

@@ -45 +45 @@
     
     JS_EXPORT_PRIVATE static bool deleteProperty(JSCell*, ExecState*, PropertyName);
-    JS_EXPORT_PRIVATE static void getOwnPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
+    JS_EXPORT_PRIVATE static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
     
 protected:

trunk/Source/JavaScriptCore/runtime/JSTypeInfo.h

@@ -43 +43 @@
     static const unsigned IsEnvironmentRecord = 1 << 4;
     static const unsigned OverridesGetOwnPropertySlot = 1 << 5;
-    static const unsigned OverridesVisitChildren = 1 << 6;
-    static const unsigned OverridesGetPropertyNames = 1 << 7;
-    static const unsigned ProhibitsPropertyCaching = 1 << 8;
+    static const unsigned InterceptsGetOwnPropertySlotByIndexEvenWhenLengthIsNotZero = 1 << 6;
+    static const unsigned OverridesVisitChildren = 1 << 7;
+    static const unsigned OverridesGetPropertyNames = 1 << 8;
+    static const unsigned ProhibitsPropertyCaching = 1 << 9;
 
     class TypeInfo {
@@ -76 +77 @@
         bool implementsDefaultHasInstance() const { return isSetOnFlags1(ImplementsDefaultHasInstance); }
         bool overridesGetOwnPropertySlot() const { return isSetOnFlags1(OverridesGetOwnPropertySlot); }
+        bool interceptsGetOwnPropertySlotByIndexEvenWhenLengthIsNotZero() const { return isSetOnFlags1(InterceptsGetOwnPropertySlotByIndexEvenWhenLengthIsNotZero); }
         bool overridesVisitChildren() const { return isSetOnFlags1(OverridesVisitChildren); }
-        bool overridesGetPropertyNames() const { return isSetOnFlags1(OverridesGetPropertyNames); }
+        bool overridesGetPropertyNames() const { return isSetOnFlags2(OverridesGetPropertyNames); }
         bool prohibitsPropertyCaching() const { return isSetOnFlags2(ProhibitsPropertyCaching); }
 

trunk/Source/JavaScriptCore/runtime/LiteralParser.cpp

@@ -28 +28 @@
 #include "LiteralParser.h"
 
+#include "ButterflyInlineMethods.h"
+#include "CopiedSpaceInlineMethods.h"
 #include "JSArray.h"
 #include "JSString.h"
@@ -641 +643 @@
             case DoParseObjectEndExpression:
             {
-                asObject(objectStack.last())->putDirect(m_exec->globalData(), identifierStack.last(), lastValue);
+                JSObject* object = asObject(objectStack.last());
+                PropertyName ident = identifierStack.last();
+                unsigned i = ident.asIndex();
+                if (i != PropertyName::NotAnIndex)
+                    object->putDirectIndex(m_exec, i, lastValue);
+                else
+                    object->putDirect(m_exec->globalData(), ident, lastValue);
                 identifierStack.removeLast();
                 if (m_lexer.currentToken().type == TokComma)

trunk/Source/JavaScriptCore/runtime/ObjectConstructor.cpp

@@ -22 +22 @@
 #include "ObjectConstructor.h"
 
+#include "ButterflyInlineMethods.h"
+#include "CopiedSpaceInlineMethods.h"
 #include "Error.h"
 #include "ExceptionHelpers.h"

trunk/Source/JavaScriptCore/runtime/ObjectPrototype.cpp

@@ -68 +68 @@
 ObjectPrototype::ObjectPrototype(ExecState* exec, Structure* stucture)
     : JSNonFinalObject(exec->globalData(), stucture)
-    , m_hasNoPropertiesWithUInt32Names(true)
 {
 }
@@ -76 +75 @@
     Base::finishCreation(globalData);
     ASSERT(inherits(&s_info));
-}
-
-void ObjectPrototype::put(JSCell* cell, ExecState* exec, PropertyName propertyName, JSValue value, PutPropertySlot& slot)
-{
-    ObjectPrototype* thisObject = jsCast<ObjectPrototype*>(cell);
-    Base::put(cell, exec, propertyName, value, slot);
-
-    if (thisObject->m_hasNoPropertiesWithUInt32Names && propertyName.asIndex() != PropertyName::NotAnIndex)
-        thisObject->m_hasNoPropertiesWithUInt32Names = false;
-}
-
-bool ObjectPrototype::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor, bool shouldThrow)
-{
-    ObjectPrototype* thisObject = jsCast<ObjectPrototype*>(object);
-    bool result = Base::defineOwnProperty(object, exec, propertyName, descriptor, shouldThrow);
-
-    if (thisObject->m_hasNoPropertiesWithUInt32Names && propertyName.asIndex() != PropertyName::NotAnIndex)
-        thisObject->m_hasNoPropertiesWithUInt32Names = false;
-
-    return result;
-}
-
-bool ObjectPrototype::getOwnPropertySlotByIndex(JSCell* cell, ExecState* exec, unsigned propertyName, PropertySlot& slot)
-{
-    ObjectPrototype* thisObject = jsCast<ObjectPrototype*>(cell);
-    if (thisObject->m_hasNoPropertiesWithUInt32Names)
-        return false;
-    return Base::getOwnPropertySlotByIndex(thisObject, exec, propertyName, slot);
 }
 

trunk/Source/JavaScriptCore/runtime/ObjectPrototype.h

@@ -51 +51 @@
     private:
         ObjectPrototype(ExecState*, Structure*);
-        static void put(JSCell*, ExecState*, PropertyName, JSValue, PutPropertySlot&);
-        static bool defineOwnProperty(JSObject*, ExecState*, PropertyName, PropertyDescriptor&, bool shouldThrow);
-
         static bool getOwnPropertySlot(JSCell*, ExecState*, PropertyName, PropertySlot&);
-        static bool getOwnPropertySlotByIndex(JSCell*, ExecState*, unsigned propertyName, PropertySlot&);
         static bool getOwnPropertyDescriptor(JSObject*, ExecState*, PropertyName, PropertyDescriptor&);
-
-        bool m_hasNoPropertiesWithUInt32Names;
     };
 

trunk/Source/JavaScriptCore/runtime/PropertyOffset.h

@@ -119 +119 @@
     validateOffset(offset);
     ASSERT(isOutOfLineOffset(offset));
-    return -static_cast<ptrdiff_t>(offset - firstOutOfLineOffset) - 2;
+    return -static_cast<ptrdiff_t>(offset - firstOutOfLineOffset) - 1;
 }
 

trunk/Source/JavaScriptCore/runtime/RegExpMatchesArray.cpp

@@ -27 +27 @@
 #include "RegExpMatchesArray.h"
 
+#include "ButterflyInlineMethods.h"
+#include "SparseArrayValueMapInlineMethods.h"
+
 namespace JSC {
 
@@ -33 +36 @@
 const ClassInfo RegExpMatchesArray::s_info = {"Array", &JSArray::s_info, 0, 0, CREATE_METHOD_TABLE(RegExpMatchesArray)};
 
+RegExpMatchesArray::RegExpMatchesArray(JSGlobalData& globalData, Butterfly* butterfly, JSGlobalObject* globalObject, JSString* input, RegExp* regExp, MatchResult result)
+    : JSArray(globalData, globalObject->regExpMatchesArrayStructure(), butterfly)
+    , m_result(result)
+    , m_state(ReifiedNone)
+{
+    m_input.set(globalData, this, input);
+    m_regExp.set(globalData, this, regExp);
+}
+
+RegExpMatchesArray* RegExpMatchesArray::create(ExecState* exec, JSString* input, RegExp* regExp, MatchResult result)
+{
+    ASSERT(result);
+    JSGlobalData& globalData = exec->globalData();
+    Butterfly* butterfly = createArrayButterfly(globalData, regExp->numSubpatterns() + 1);
+    RegExpMatchesArray* array = new (NotNull, allocateCell<RegExpMatchesArray>(globalData.heap)) RegExpMatchesArray(globalData, butterfly, exec->lexicalGlobalObject(), input, regExp, result);
+    array->finishCreation(globalData);
+    return array;
+}
+
 void RegExpMatchesArray::finishCreation(JSGlobalData& globalData)
 {
-    Base::finishCreation(globalData, m_regExp->numSubpatterns() + 1);
+    Base::finishCreation(globalData);
 }
 

trunk/Source/JavaScriptCore/runtime/RegExpMatchesArray.h

@@ -29 +29 @@
     class RegExpMatchesArray : public JSArray {
     private:
-        RegExpMatchesArray(JSGlobalData& globalData, JSGlobalObject* globalObject, JSString* input, RegExp* regExp, MatchResult result)
-            : JSArray(globalData, globalObject->regExpMatchesArrayStructure())
-            , m_result(result)
-            , m_state(ReifiedNone)
-        {
-            m_input.set(globalData, this, input);
-            m_regExp.set(globalData, this, regExp);
-        }
+        RegExpMatchesArray(JSGlobalData&, Butterfly*, JSGlobalObject*, JSString*, RegExp*, MatchResult);
 
         enum ReifiedState { ReifiedNone, ReifiedMatch, ReifiedAll };
@@ -43 +36 @@
         typedef JSArray Base;
 
-        static RegExpMatchesArray* create(ExecState* exec, JSString* input, RegExp* regExp, MatchResult result)
-        {
-            ASSERT(result);
-            JSGlobalData& globalData = exec->globalData();
-            RegExpMatchesArray* array = new (NotNull, allocateCell<RegExpMatchesArray>(globalData.heap)) RegExpMatchesArray(globalData, exec->lexicalGlobalObject(), input, regExp, result);
-            array->finishCreation(globalData);
-            return array;
-        }
+        static RegExpMatchesArray* create(ExecState*, JSString*, RegExp*, MatchResult);
 
         JSString* leftContext(ExecState*);
@@ -59 +45 @@
         static Structure* createStructure(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype)
         {
-            return Structure::create(globalData, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), &s_info);
+            return Structure::create(globalData, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), &s_info, ArrayWithArrayStorage);
         }
 

trunk/Source/JavaScriptCore/runtime/RegExpObject.cpp

@@ -22 +22 @@
 #include "RegExpObject.h"
 
+#include "ButterflyInlineMethods.h"
+#include "CopiedSpaceInlineMethods.h"
 #include "Error.h"
 #include "ExceptionHelpers.h"
@@ -114 +116 @@
 }
 
-void RegExpObject::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
+void RegExpObject::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
 {
     if (mode == IncludeDontEnumProperties)
         propertyNames.add(exec->propertyNames().lastIndex);
-    Base::getOwnPropertyNames(object, exec, propertyNames, mode);
+    Base::getOwnNonIndexPropertyNames(object, exec, propertyNames, mode);
 }
 

trunk/Source/JavaScriptCore/runtime/RegExpObject.h

@@ -91 +91 @@
 
         JS_EXPORT_PRIVATE static bool deleteProperty(JSCell*, ExecState*, PropertyName);
-        JS_EXPORT_PRIVATE static void getOwnPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
+        JS_EXPORT_PRIVATE static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
         JS_EXPORT_PRIVATE static void getPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
         JS_EXPORT_PRIVATE static bool defineOwnProperty(JSObject*, ExecState*, PropertyName, PropertyDescriptor&, bool shouldThrow);

trunk/Source/JavaScriptCore/runtime/StringObject.cpp

@@ -79 +79 @@
 }
 
+void StringObject::putByIndex(JSCell* cell, ExecState* exec, unsigned propertyName, JSValue value, bool shouldThrow)
+{
+    StringObject* thisObject = jsCast<StringObject*>(cell);
+    if (thisObject->internalValue()->canGetIndex(propertyName)) {
+        if (shouldThrow)
+            throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
+        return;
+    }
+    JSObject::putByIndex(cell, exec, propertyName, value, shouldThrow);
+}
+
 bool StringObject::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor, bool throwException)
 {
@@ -134 +145 @@
 }
 
+bool StringObject::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned i)
+{
+    StringObject* thisObject = jsCast<StringObject*>(cell);
+    if (thisObject->internalValue()->canGetIndex(i))
+        return false;
+    return JSObject::deletePropertyByIndex(thisObject, exec, i);
+}
+
 void StringObject::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
 {

trunk/Source/JavaScriptCore/runtime/StringObject.h

@@ -51 +51 @@
 
         static void put(JSCell*, ExecState*, PropertyName, JSValue, PutPropertySlot&);
+        static void putByIndex(JSCell*, ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
 
         static bool deleteProperty(JSCell*, ExecState*, PropertyName);
+        static bool deletePropertyByIndex(JSCell*, ExecState*, unsigned propertyName);
         static void getOwnPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
         static bool defineOwnProperty(JSObject*, ExecState*, PropertyName, PropertyDescriptor&, bool shouldThrow);
@@ -67 +69 @@
     protected:
         JS_EXPORT_PRIVATE void finishCreation(JSGlobalData&, JSString*);
-        static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesGetPropertyNames | JSWrapperObject::StructureFlags;
+        static const unsigned StructureFlags = OverridesGetOwnPropertySlot | InterceptsGetOwnPropertySlotByIndexEvenWhenLengthIsNotZero | OverridesGetPropertyNames | JSWrapperObject::StructureFlags;
         JS_EXPORT_PRIVATE StringObject(JSGlobalData&, Structure*);
     };

trunk/Source/JavaScriptCore/runtime/StringPrototype.cpp

@@ -23 +23 @@
 #include "StringPrototype.h"
 
+#include "ButterflyInlineMethods.h"
 #include "CachedCall.h"
+#include "CopiedSpaceInlineMethods.h"
 #include "Error.h"
 #include "Executable.h"

trunk/Source/JavaScriptCore/runtime/Structure.cpp

@@ -150 +150 @@
 }
 
-Structure::Structure(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype, const TypeInfo& typeInfo, const ClassInfo* classInfo)
+Structure::Structure(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype, const TypeInfo& typeInfo, const ClassInfo* classInfo, IndexingType indexingType)
     : JSCell(globalData, globalData.structureStructure.get())
     , m_typeInfo(typeInfo)
+    , m_indexingType(indexingType)
     , m_globalObject(globalData, this, globalObject, WriteBarrier<JSGlobalObject>::MayBeNull)
     , m_prototype(globalData, this, prototype)
@@ -177 +178 @@
     : JSCell(CreatingEarlyCell)
     , m_typeInfo(CompoundType, OverridesVisitChildren)
+    , m_indexingType(0)
     , m_prototype(globalData, this, jsNull())
     , m_classInfo(&s_info)
@@ -198 +200 @@
     : JSCell(globalData, globalData.structureStructure.get())
     , m_typeInfo(previous->typeInfo())
+    , m_indexingType(previous->indexingTypeIncludingHistory())
     , m_prototype(globalData, this, previous->storedPrototype())
     , m_classInfo(previous->m_classInfo)
@@ -252 +255 @@
     for (ptrdiff_t i = structures.size() - 2; i >= 0; --i) {
         structure = structures[i];
+        if (!structure->m_nameInPrevious)
+            continue;
         PropertyMapEntry entry(globalData, this, structure->m_nameInPrevious.get(), structure->m_offset, structure->m_attributesInPrevious, structure->m_specificValueInPrevious.get());
         m_propertyTable->add(entry);
@@ -500 +505 @@
     transition->pin();
 
+    return transition;
+}
+
+Structure* Structure::nonPropertyTransition(JSGlobalData& globalData, Structure* structure, NonPropertyTransition transitionKind)
+{
+    unsigned attributes = toAttributes(transitionKind);
+    IndexingType indexingType = newIndexingType(structure->indexingTypeIncludingHistory(), transitionKind);
+    
+    if (Structure* existingTransition = structure->m_transitionTable.get(0, attributes)) {
+        ASSERT(existingTransition->m_attributesInPrevious == attributes);
+        ASSERT(existingTransition->indexingTypeIncludingHistory() == indexingType);
+        return existingTransition;
+    }
+    
+    Structure* transition = create(globalData, structure);
+    transition->m_previous.set(globalData, transition, structure);
+    transition->m_attributesInPrevious = attributes;
+    transition->m_indexingType = indexingType;
+    
+    if (structure->m_propertyTable) {
+        if (structure->m_isPinnedPropertyTable)
+            transition->m_propertyTable = structure->m_propertyTable->copy(globalData, transition, structure->m_propertyTable->size() + 1);
+        else
+            transition->m_propertyTable = structure->m_propertyTable.release();
+    } else {
+        if (structure->m_previous)
+            transition->materializePropertyMap(globalData);
+        else
+            transition->createPropertyMap();
+    }
+    
+    structure->m_transitionTable.add(globalData, transition);
     return transition;
 }

trunk/Source/JavaScriptCore/runtime/Structure.h

@@ -28 +28 @@
 
 #include "ClassInfo.h"
+#include "IndexingType.h"
 #include "JSCell.h"
 #include "JSType.h"
@@ -69 +70 @@
         typedef JSCell Base;
 
-        static Structure* create(JSGlobalData&, JSGlobalObject*, JSValue prototype, const TypeInfo&, const ClassInfo*);
+        static Structure* create(JSGlobalData&, JSGlobalObject*, JSValue prototype, const TypeInfo&, const ClassInfo*, IndexingType = 0);
 
     protected:
@@ -101 +102 @@
         static Structure* freezeTransition(JSGlobalData&, Structure*);
         static Structure* preventExtensionsTransition(JSGlobalData&, Structure*);
+        static Structure* nonPropertyTransition(JSGlobalData&, Structure*, NonPropertyTransition);
 
         bool isSealed(JSGlobalData&);
@@ -141 +143 @@
         bool isObject() const { return typeInfo().isObject(); }
 
+        IndexingType indexingType() const { return m_indexingType & AllArrayTypes; }
+        IndexingType indexingTypeIncludingHistory() const { return m_indexingType; }
 
         JSGlobalObject* globalObject() const { return m_globalObject.get(); }
@@ -335 +339 @@
             return OBJECT_OFFSETOF(Structure, m_classInfo);
         }
+        
+        static ptrdiff_t indexingTypeOffset()
+        {
+            return OBJECT_OFFSETOF(Structure, m_indexingType);
+        }
 
         static Structure* createStructure(JSGlobalData&);
@@ -364 +373 @@
         friend class LLIntOffsetsExtractor;
 
-        JS_EXPORT_PRIVATE Structure(JSGlobalData&, JSGlobalObject*, JSValue prototype, const TypeInfo&, const ClassInfo*);
+        JS_EXPORT_PRIVATE Structure(JSGlobalData&, JSGlobalObject*, JSValue prototype, const TypeInfo&, const ClassInfo*, IndexingType = 0);
         Structure(JSGlobalData&);
         Structure(JSGlobalData&, const Structure*);
@@ -417 +426 @@
 
         TypeInfo m_typeInfo;
+        IndexingType m_indexingType;
         
         WriteBarrier<JSGlobalObject> m_globalObject;
@@ -448 +458 @@
         bool m_hasReadOnlyOrGetterSetterPropertiesExcludingProto : 1;
         bool m_hasNonEnumerableProperties : 1;
-        unsigned m_attributesInPrevious : 7;
+        unsigned m_attributesInPrevious : 22;
         unsigned m_specificFunctionThrashCount : 2;
         unsigned m_preventExtensions : 1;
@@ -466 +476 @@
     }
 
-    inline Structure* Structure::create(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype, const TypeInfo& typeInfo, const ClassInfo* classInfo)
+    inline Structure* Structure::create(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype, const TypeInfo& typeInfo, const ClassInfo* classInfo, IndexingType indexingType)
     {
         ASSERT(globalData.structureStructure);
         ASSERT(classInfo);
-        Structure* structure = new (NotNull, allocateCell<Structure>(globalData.heap)) Structure(globalData, globalObject, prototype, typeInfo, classInfo);
+        Structure* structure = new (NotNull, allocateCell<Structure>(globalData.heap)) Structure(globalData, globalObject, prototype, typeInfo, classInfo, indexingType);
         structure->finishCreation(globalData);
         return structure;

trunk/Source/JavaScriptCore/runtime/StructureTransitionTable.h

@@ -27 +27 @@
 #define StructureTransitionTable_h
 
+#include "IndexingType.h"
 #include "WeakGCMap.h"
 #include <wtf/HashFunctions.h>
@@ -38 +39 @@
 class Structure;
 
+static const unsigned FirstInternalAttribute = 1 << 6; // Use for transitions that don't have to do with property additions.
+
+// Support for attributes used to indicate transitions not related to properties.
+// If any of these are used, the string portion of the key should be 0.
+enum NonPropertyTransition {
+    AllocateArrayStorage
+};
+
+inline unsigned toAttributes(NonPropertyTransition transition)
+{
+    return transition + FirstInternalAttribute;
+}
+
+inline IndexingType newIndexingType(IndexingType oldType, NonPropertyTransition transition)
+{
+    switch (transition) {
+    case AllocateArrayStorage:
+        return oldType | HasArrayStorage;
+    default:
+        ASSERT_NOT_REACHED();
+        return oldType;
+    }
+}
+
 class StructureTransitionTable {
     static const intptr_t UsingSingleSlotFlag = 1;
@@ -45 +70 @@
         static unsigned hash(const Key& p)
         {
-            return p.first->existingHash();
+            unsigned result = p.second;
+            if (p.first)
+                result += p.first->existingHash();
+            return result;
         }