Ignore:
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.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/runtime/JSArray.h

    r127349 r128400  
    11/*
    22 *  Copyright (C) 1999-2000 Harri Porten ([email protected])
    3  *  Copyright (C) 2003, 2007, 2008, 2009 Apple Inc. All rights reserved.
     3 *  Copyright (C) 2003, 2007, 2008, 2009, 2012 Apple Inc. All rights reserved.
    44 *
    55 *  This library is free software; you can redistribute it and/or
    … …  
    2222#define JSArray_h
    2323
     24#include "ArrayConventions.h"
     25#include "ButterflyInlineMethods.h"
    2426#include "JSObject.h"
    25 
    26 #define CHECK_ARRAY_CONSISTENCY 0
    2727
    2828namespace JSC {
    … …  
    3030    class JSArray;
    3131    class LLIntOffsetsExtractor;
    32 
    33     enum PutDirectIndexMode { PutDirectIndexLikePutDirect, PutDirectIndexShouldNotThrow, PutDirectIndexShouldThrow };
    34 
    35     struct SparseArrayEntry : public WriteBarrier<Unknown> {
    36         typedef WriteBarrier<Unknown> Base;
    37 
    38         SparseArrayEntry() : attributes(0) {}
    39 
    40         JSValue get(ExecState*, JSArray*) const;
    41         void get(PropertySlot&) const;
    42         void get(PropertyDescriptor&) const;
    43         JSValue getNonSparseMode() const;
    44 
    45         unsigned attributes;
    46     };
    47 
    48     class SparseArrayValueMap {
    49         typedef HashMap<uint64_t, SparseArrayEntry, WTF::IntHash<uint64_t>, WTF::UnsignedWithZeroKeyHashTraits<uint64_t> > Map;
    50 
    51         enum Flags {
    52             Normal = 0,
    53             SparseMode = 1,
    54             LengthIsReadOnly = 2,
    55         };
    56 
    57     public:
    58         typedef Map::iterator iterator;
    59         typedef Map::const_iterator const_iterator;
    60         typedef Map::AddResult AddResult;
    61 
    62         SparseArrayValueMap()
    63             : m_flags(Normal)
    64             , m_reportedCapacity(0)
    65         {
    66         }
    67 
    68         void visitChildren(SlotVisitor&);
    69 
    70         bool sparseMode()
    71         {
    72             return m_flags & SparseMode;
    73         }
    74 
    75         void setSparseMode()
    76         {
    77             m_flags = static_cast<Flags>(m_flags | SparseMode);
    78         }
    79 
    80         bool lengthIsReadOnly()
    81         {
    82             return m_flags & LengthIsReadOnly;
    83         }
    84 
    85         void setLengthIsReadOnly()
    86         {
    87             m_flags = static_cast<Flags>(m_flags | LengthIsReadOnly);
    88         }
    89 
    90         // These methods may mutate the contents of the map
    91         void put(ExecState*, JSArray*, unsigned, JSValue, bool shouldThrow);
    92         bool putDirect(ExecState*, JSArray*, unsigned, JSValue, PutDirectIndexMode);
    93         AddResult add(JSArray*, unsigned);
    94         iterator find(unsigned i) { return m_map.find(i); }
    95         // This should ASSERT the remove is valid (check the result of the find).
    96         void remove(iterator it) { m_map.remove(it); }
    97         void remove(unsigned i) { m_map.remove(i); }
    98 
    99         // These methods do not mutate the contents of the map.
    100         iterator notFound() { return m_map.end(); }
    101         bool isEmpty() const { return m_map.isEmpty(); }
    102         bool contains(unsigned i) const { return m_map.contains(i); }
    103         size_t size() const { return m_map.size(); }
    104         // Only allow const begin/end iteration.
    105         const_iterator begin() const { return m_map.begin(); }
    106         const_iterator end() const { return m_map.end(); }
    107 
    108     private:
    109         Map m_map;
    110         Flags m_flags;
    111         size_t m_reportedCapacity;
    112     };
    113 
    114     // This struct holds the actual data values of an array.  A JSArray object points to it's contained ArrayStorage
    115     // struct by pointing to m_vector.  To access the contained ArrayStorage struct, use the getStorage() and
    116     // setStorage() methods.  It is important to note that there may be space before the ArrayStorage that
    117     // is used to quick unshift / shift operation.  The actual allocated pointer is available by using:
    118     //     getStorage() - m_indexBias * sizeof(JSValue)
    119     struct ArrayStorage {
    120         unsigned m_length; // The "length" property on the array
    121         unsigned m_numValuesInVector;
    122         void* m_allocBase; // Pointer to base address returned by malloc().  Keeping this pointer does eliminate false positives from the leak detector.
    123 #if CHECK_ARRAY_CONSISTENCY
    124         // Needs to be a uintptr_t for alignment purposes.
    125         uintptr_t m_initializationIndex;
    126         uintptr_t m_inCompactInitialization;
    127 #else
    128         uintptr_t m_padding;
    129 #endif
    130         WriteBarrier<Unknown> m_vector[1];
    131 
    132         static ptrdiff_t lengthOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_length); }
    133         static ptrdiff_t numValuesInVectorOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_numValuesInVector); }
    134         static ptrdiff_t allocBaseOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_allocBase); }
    135         static ptrdiff_t vectorOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_vector); }
    136     };
    13732
    13833    class JSArray : public JSNonFinalObject {
    … …  
    14136        friend class JIT;
    14237
     38    public:
     39        typedef JSNonFinalObject Base;
     40
    14341    protected:
    144         explicit JSArray(JSGlobalData& globalData, Structure* structure)
    145             : JSNonFinalObject(globalData, structure)
    146             , m_indexBias(0)
    147             , m_storage(0)
    148             , m_sparseValueMap(0)
     42        explicit JSArray(JSGlobalData& globalData, Structure* structure, Butterfly* butterfly)
     43            : JSNonFinalObject(globalData, structure, butterfly)
    14944        {
    15045        }
    15146
    152         JS_EXPORT_PRIVATE void finishCreation(JSGlobalData&, unsigned initialLength = 0);
    153         JS_EXPORT_PRIVATE JSArray* tryFinishCreationUninitialized(JSGlobalData&, unsigned initialLength);
    154    
    15547    public:
    156         typedef JSNonFinalObject Base;
    157 
    158         static void finalize(JSCell*);
    159 
    16048        static JSArray* create(JSGlobalData&, Structure*, unsigned initialLength = 0);
    16149
    … …  
    17058
    17159        static bool getOwnPropertySlot(JSCell*, ExecState*, PropertyName, PropertySlot&);
    172         JS_EXPORT_PRIVATE static bool getOwnPropertySlotByIndex(JSCell*, ExecState*, unsigned propertyName, PropertySlot&);
    17360        static bool getOwnPropertyDescriptor(JSObject*, ExecState*, PropertyName, PropertyDescriptor&);
    174         static void putByIndex(JSCell*, ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
    175         // This is similar to the JSObject::putDirect* methods:
    176         //  - the prototype chain is not consulted
    177         //  - accessors are not called.
    178         //  - it will ignore extensibility and read-only properties if PutDirectIndexLikePutDirect is passed as the mode (the default).
    179         // This method creates a property with attributes writable, enumerable and configurable all set to true.
    180         bool putDirectIndex(ExecState* exec, unsigned propertyName, JSValue value, PutDirectIndexMode mode = PutDirectIndexLikePutDirect)
    181         {
    182             if (canSetIndex(propertyName)) {
    183                 setIndex(exec->globalData(), propertyName, value);
    184                 return true;
    185             }
    186             return putDirectIndexBeyondVectorLength(exec, propertyName, value, mode);
    187         }
    18861
    18962        static JS_EXPORTDATA const ClassInfo s_info;
    19063       
    191         unsigned length() const { return m_storage->m_length; }
     64        unsigned length() const { return getArrayLength(); }
    19265        // OK to use on new arrays, but not if it might be a RegExpMatchArray.
    19366        bool setLength(ExecState*, unsigned, bool throwException = false);
    … …  
    20376        bool unshiftCount(ExecState*, unsigned count);
    20477
    205         bool canGetIndex(unsigned i) { return i < m_vectorLength && m_storage->m_vector[i]; }
    206         JSValue getIndex(unsigned i)
    207         {
    208             ASSERT(canGetIndex(i));
    209             return m_storage->m_vector[i].get();
    210         }
    211 
    212         bool canSetIndex(unsigned i) { return i < m_vectorLength; }
    213         void setIndex(JSGlobalData& globalData, unsigned i, JSValue v)
    214         {
    215             ASSERT(canSetIndex(i));
    216            
    217             WriteBarrier<Unknown>& x = m_storage->m_vector[i];
    218             if (!x) {
    219                 ArrayStorage *storage = m_storage;
    220                 ++storage->m_numValuesInVector;
    221                 if (i >= storage->m_length)
    222                     storage->m_length = i + 1;
    223             }
    224             x.set(globalData, this, v);
    225         }
    226        
    227         inline void initializeIndex(JSGlobalData& globalData, unsigned i, JSValue v)
    228         {
    229             ASSERT(canSetIndex(i));
    230             ArrayStorage *storage = m_storage;
    231 #if CHECK_ARRAY_CONSISTENCY
    232             ASSERT(storage->m_inCompactInitialization);
    233             // Check that we are initializing the next index in sequence.
    234             ASSERT(i == storage->m_initializationIndex);
    235             // tryCreateUninitialized set m_numValuesInVector to the initialLength,
    236             // check we do not try to initialize more than this number of properties.
    237             ASSERT(storage->m_initializationIndex < storage->m_numValuesInVector);
    238             storage->m_initializationIndex++;
    239 #endif
    240             ASSERT(i < storage->m_length);
    241             ASSERT(i < storage->m_numValuesInVector);
    242             storage->m_vector[i].set(globalData, this, v);
    243         }
    244 
    245         inline void completeInitialization(unsigned newLength)
    246         {
    247             // Check that we have initialized as meny properties as we think we have.
    248             ASSERT_UNUSED(newLength, newLength == m_storage->m_length);
    249 #if CHECK_ARRAY_CONSISTENCY
    250             // Check that the number of propreties initialized matches the initialLength.
    251             ASSERT(m_storage->m_initializationIndex == m_storage->m_numValuesInVector);
    252             ASSERT(m_storage->m_inCompactInitialization);
    253             m_storage->m_inCompactInitialization = false;
    254 #endif
    255         }
    256 
    257         bool inSparseMode()
    258         {
    259             SparseArrayValueMap* map = m_sparseValueMap;
    260             return map && map->sparseMode();
    261         }
    262 
    26378        void fillArgList(ExecState*, MarkedArgumentBuffer&);
    26479        void copyToArguments(ExecState*, CallFrame*, uint32_t length);
    … …  
    26681        static Structure* createStructure(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype)
    26782        {
    268             return Structure::create(globalData, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), &s_info);
     83            return Structure::create(globalData, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), &s_info, ArrayWithArrayStorage);
    26984        }
    27085       
    271         static ptrdiff_t storageOffset()
    272         {
    273             return OBJECT_OFFSETOF(JSArray, m_storage);
    274         }
    275 
    276         static ptrdiff_t vectorLengthOffset()
    277         {
    278             return OBJECT_OFFSETOF(JSArray, m_vectorLength);
    279         }
    280 
    281         JS_EXPORT_PRIVATE static void visitChildren(JSCell*, SlotVisitor&);
    282 
    283         void enterDictionaryMode(JSGlobalData&);
    284 
    28586    protected:
    286         static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesVisitChildren | OverridesGetPropertyNames | JSObject::StructureFlags;
     87        static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesGetPropertyNames | JSObject::StructureFlags;
    28788        static void put(JSCell*, ExecState*, PropertyName, JSValue, PutPropertySlot&);
    28889
    28990        static bool deleteProperty(JSCell*, ExecState*, PropertyName);
    290         static bool deletePropertyByIndex(JSCell*, ExecState*, unsigned propertyName);
    291         static void getOwnPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
     91        JS_EXPORT_PRIVATE static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
    29292
    29393    private:
    294         static size_t storageSize(unsigned vectorLength);
    29594        bool isLengthWritable()
    29695        {
    297             SparseArrayValueMap* map = m_sparseValueMap;
     96            ArrayStorage* storage = arrayStorageOrNull();
     97            if (!storage)
     98                return false;
     99            SparseArrayValueMap* map = storage->m_sparseMap.get();
    298100            return !map || !map->lengthIsReadOnly();
    299101        }
    300102
    301103        void setLengthWritable(ExecState*, bool writable);
    302         void putDescriptor(ExecState*, SparseArrayEntry*, PropertyDescriptor&, PropertyDescriptor& old);
    303         bool defineOwnNumericProperty(ExecState*, unsigned, PropertyDescriptor&, bool throwException);
    304         void allocateSparseMap(JSGlobalData&);
    305         void deallocateSparseMap();
    306 
    307         void putByIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
    308         JS_EXPORT_PRIVATE bool putDirectIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, PutDirectIndexMode);
    309 
    310         unsigned getNewVectorLength(unsigned desiredLength);
    311         bool increaseVectorLength(JSGlobalData&, unsigned newLength);
     104
    312105        bool unshiftCountSlowCase(JSGlobalData&, unsigned count);
    313106       
    314107        unsigned compactForSorting(JSGlobalData&);
    315 
    316         enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck };
    317         void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck);
    318 
    319         unsigned m_vectorLength; // The valid length of m_vector
    320         unsigned m_indexBias; // The number of JSValue sized blocks before ArrayStorage.
    321         ArrayStorage *m_storage;
    322 
    323         // FIXME: Maybe SparseArrayValueMap should be put into its own JSCell?
    324         SparseArrayValueMap* m_sparseValueMap;
    325 
    326         static ptrdiff_t sparseValueMapOffset() { return OBJECT_OFFSETOF(JSArray, m_sparseValueMap); }
    327         static ptrdiff_t indexBiasOffset() { return OBJECT_OFFSETOF(JSArray, m_indexBias); }
    328108    };
    329109
     110    inline Butterfly* createArrayButterfly(JSGlobalData& globalData, unsigned initialLength)
     111    {
     112        Butterfly* butterfly = Butterfly::create(
     113            globalData, 0, 0, true, baseIndexingHeaderForArray(initialLength), ArrayStorage::sizeFor(BASE_VECTOR_LEN));
     114        ArrayStorage* storage = butterfly->arrayStorage();
     115        storage->m_indexBias = 0;
     116        storage->m_sparseMap.clear();
     117        storage->m_numValuesInVector = 0;
     118#if CHECK_ARRAY_CONSISTENCY
     119        storage->m_initializationIndex = 0;
     120        storage->m_inCompactInitialization = 0;
     121#endif
     122        return butterfly;
     123    }
     124
     125    Butterfly* createArrayButterflyInDictionaryIndexingMode(JSGlobalData&, unsigned initialLength);
     126
    330127    inline JSArray* JSArray::create(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
    331128    {
    332         JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
    333         array->finishCreation(globalData, initialLength);
     129        Butterfly* butterfly = createArrayButterfly(globalData, initialLength);
     130        JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure, butterfly);
     131        array->finishCreation(globalData);
    334132        return array;
    335133    }
    … …  
    337135    inline JSArray* JSArray::tryCreateUninitialized(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
    338136    {
    339         JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
    340         return array->tryFinishCreationUninitialized(globalData, initialLength);
     137        unsigned vectorLength = std::max(BASE_VECTOR_LEN, initialLength);
     138        if (vectorLength > MAX_STORAGE_VECTOR_LENGTH)
     139            return 0;
     140       
     141        void* temp;
     142        if (!globalData.heap.tryAllocateStorage(Butterfly::totalSize(0, 0, true, ArrayStorage::sizeFor(vectorLength)), &temp))
     143            return 0;
     144        Butterfly* butterfly = Butterfly::fromBase(temp, 0, 0);
     145        *butterfly->indexingHeader() = indexingHeaderForArray(initialLength, vectorLength);
     146        ArrayStorage* storage = butterfly->arrayStorage();
     147        storage->m_indexBias = 0;
     148        storage->m_sparseMap.clear();
     149        storage->m_numValuesInVector = initialLength;
     150#if CHECK_ARRAY_CONSISTENCY
     151        storage->m_initializationIndex = 0;
     152        storage->m_inCompactInitialization = true;
     153#endif
     154       
     155        JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure, butterfly);
     156        array->finishCreation(globalData);
     157        return array;
    341158    }
    342159
    … …  
    356173    inline bool isJSArray(JSCell* cell) { return cell->classInfo() == &JSArray::s_info; }
    357174    inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); }
    358 
    359 // The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
    360 // function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
    361 // size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) +
    362 // (vectorLength * sizeof(WriteBarrier<Unknown>)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
    363 #define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>))
    364 
    365 // These values have to be macros to be used in max() and min() without introducing
    366 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
    367 #define MIN_SPARSE_ARRAY_INDEX 10000U
    368 #define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
    369     inline size_t JSArray::storageSize(unsigned vectorLength)
    370     {
    371         ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH);
    372    
    373         // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH)
    374         // - as asserted above - the following calculation cannot overflow.
    375         size_t size = (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) + (vectorLength * sizeof(WriteBarrier<Unknown>));
    376         // Assertion to detect integer overflow in previous calculation (should not be possible, provided that
    377         // MAX_STORAGE_VECTOR_LENGTH is correctly defined).
    378         ASSERT(((size - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))));
    379    
    380         return size;
    381     }
    382175
    383176    inline JSArray* constructArray(ExecState* exec, Structure* arrayStructure, const ArgList& values)
Note: See TracChangeset for help on using the changeset viewer.