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.
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@128400 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/JavaScriptCore/runtime/JSArray.h b/Source/JavaScriptCore/runtime/JSArray.h
index 2aab8c6..d382f64 100644
--- a/Source/JavaScriptCore/runtime/JSArray.h
+++ b/Source/JavaScriptCore/runtime/JSArray.h
@@ -1,6 +1,6 @@
/*
* Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
- * 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
* modify it under the terms of the GNU Lesser General Public
@@ -21,142 +21,30 @@
#ifndef JSArray_h
#define JSArray_h
+#include "ArrayConventions.h"
+#include "ButterflyInlineMethods.h"
#include "JSObject.h"
-#define CHECK_ARRAY_CONSISTENCY 0
-
namespace JSC {
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 {
friend class LLIntOffsetsExtractor;
friend class Walker;
friend class JIT;
- protected:
- explicit JSArray(JSGlobalData& globalData, Structure* structure)
- : JSNonFinalObject(globalData, structure)
- , m_indexBias(0)
- , m_storage(0)
- , m_sparseValueMap(0)
- {
- }
-
- 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*);
+ protected:
+ explicit JSArray(JSGlobalData& globalData, Structure* structure, Butterfly* butterfly)
+ : JSNonFinalObject(globalData, structure, butterfly)
+ {
+ }
+ public:
static JSArray* create(JSGlobalData&, Structure*, unsigned initialLength = 0);
// tryCreateUninitialized is used for fast construction of arrays whose size and
@@ -169,26 +57,11 @@
JS_EXPORT_PRIVATE static bool defineOwnProperty(JSObject*, ExecState*, PropertyName, PropertyDescriptor&, bool throwException);
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);
@@ -202,142 +75,86 @@
bool shiftCount(ExecState*, unsigned count);
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);
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;
}
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;
}
JSArray* asArray(JSValue);
@@ -356,30 +173,6 @@
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)
{
JSGlobalData& globalData = exec->globalData();
