X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/f9bf01c6616d5ddcf65b13b33cedf9e387ff7a63..refs/heads/master:/runtime/JSArray.h diff --git a/runtime/JSArray.h b/runtime/JSArray.h index ad6ee88..45b558b 100644 --- a/runtime/JSArray.h +++ b/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, 2015 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,206 +21,327 @@ #ifndef JSArray_h #define JSArray_h +#include "ArrayConventions.h" +#include "ButterflyInlines.h" #include "JSObject.h" namespace JSC { - typedef HashMap SparseArrayValueMap; +class JSArray; +class LLIntOffsetsExtractor; - struct ArrayStorage { - unsigned m_length; - unsigned m_numValuesInVector; - SparseArrayValueMap* m_sparseValueMap; - void* lazyCreationData; // A JSArray subclass can use this to fill the vector lazily. - size_t reportedMapCapacity; - JSValue m_vector[1]; - }; - - class JSArray : public JSObject { - friend class JIT; - friend class Walker; - - public: - explicit JSArray(NonNullPassRefPtr); - JSArray(NonNullPassRefPtr, unsigned initialLength); - JSArray(NonNullPassRefPtr, const ArgList& initialValues); - virtual ~JSArray(); - - virtual bool getOwnPropertySlot(ExecState*, const Identifier& propertyName, PropertySlot&); - virtual bool getOwnPropertySlot(ExecState*, unsigned propertyName, PropertySlot&); - virtual bool getOwnPropertyDescriptor(ExecState*, const Identifier&, PropertyDescriptor&); - virtual void put(ExecState*, unsigned propertyName, JSValue); // FIXME: Make protected and add setItem. - - static JS_EXPORTDATA const ClassInfo info; - - unsigned length() const { return m_storage->m_length; } - void setLength(unsigned); // OK to use on new arrays, but not if it might be a RegExpMatchArray. - - void sort(ExecState*); - void sort(ExecState*, JSValue compareFunction, CallType, const CallData&); - void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&); - - void push(ExecState*, JSValue); - JSValue pop(); - - 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]; - } - - bool canSetIndex(unsigned i) { return i < m_vectorLength; } - void setIndex(unsigned i, JSValue v) - { - ASSERT(canSetIndex(i)); - JSValue& x = m_storage->m_vector[i]; - if (!x) { - ++m_storage->m_numValuesInVector; - if (i >= m_storage->m_length) - m_storage->m_length = i + 1; - } - x = v; - } +class JSArray : public JSNonFinalObject { + friend class LLIntOffsetsExtractor; + friend class Walker; + friend class JIT; - void fillArgList(ExecState*, MarkedArgumentBuffer&); - void copyToRegisters(ExecState*, Register*, uint32_t); +public: + typedef JSNonFinalObject Base; + static const unsigned StructureFlags = Base::StructureFlags | OverridesGetOwnPropertySlot | OverridesGetPropertyNames; - static PassRefPtr createStructure(JSValue prototype) - { - return Structure::create(prototype, TypeInfo(ObjectType, StructureFlags), AnonymousSlotCount); - } + static size_t allocationSize(size_t inlineCapacity) + { + ASSERT_UNUSED(inlineCapacity, !inlineCapacity); + return sizeof(JSArray); + } - inline void markChildrenDirect(MarkStack& markStack); +protected: + explicit JSArray(VM& vm, Structure* structure, Butterfly* butterfly) + : JSNonFinalObject(vm, structure, butterfly) + { + } - protected: - static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesMarkChildren | OverridesGetPropertyNames | JSObject::StructureFlags; - virtual void put(ExecState*, const Identifier& propertyName, JSValue, PutPropertySlot&); - virtual bool deleteProperty(ExecState*, const Identifier& propertyName); - virtual bool deleteProperty(ExecState*, unsigned propertyName); - virtual void getOwnPropertyNames(ExecState*, PropertyNameArray&, EnumerationMode mode = ExcludeDontEnumProperties); - virtual void markChildren(MarkStack&); +public: + static JSArray* create(VM&, Structure*, unsigned initialLength = 0); + static JSArray* createWithButterfly(VM&, Structure*, Butterfly*); - void* lazyCreationData(); - void setLazyCreationData(void*); + // tryCreateUninitialized is used for fast construction of arrays whose size and + // contents are known at time of creation. Clients of this interface must: + // - null-check the result (indicating out of memory, or otherwise unable to allocate vector). + // - call 'initializeIndex' for all properties in sequence, for 0 <= i < initialLength. + static JSArray* tryCreateUninitialized(VM&, Structure*, unsigned initialLength); - private: - virtual const ClassInfo* classInfo() const { return &info; } + JS_EXPORT_PRIVATE static bool defineOwnProperty(JSObject*, ExecState*, PropertyName, const PropertyDescriptor&, bool throwException); - bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&); - void putSlowCase(ExecState*, unsigned propertyName, JSValue); + JS_EXPORT_PRIVATE static bool getOwnPropertySlot(JSObject*, ExecState*, PropertyName, PropertySlot&); - bool increaseVectorLength(unsigned newLength); - - unsigned compactForSorting(); + DECLARE_EXPORT_INFO; - enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck }; - void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck); + // OK if we know this is a JSArray, but not if it could be an object of a derived class; for RuntimeArray this always returns 0. + unsigned length() const { return getArrayLength(); } - unsigned m_vectorLength; - ArrayStorage* m_storage; - }; + // OK to use on new arrays, but not if it might be a RegExpMatchArray or RuntimeArray. + JS_EXPORT_PRIVATE bool setLength(ExecState*, unsigned, bool throwException = false); + + JS_EXPORT_PRIVATE void push(ExecState*, JSValue); + JS_EXPORT_PRIVATE JSValue pop(ExecState*); - JSArray* asArray(JSValue); + JSArray* fastSlice(ExecState&, unsigned startIndex, unsigned count); - inline JSArray* asArray(JSCell* cell) + static IndexingType fastConcatType(VM& vm, JSArray& firstArray, JSArray& secondArray) { - ASSERT(cell->inherits(&JSArray::info)); - return static_cast(cell); + IndexingType type = firstArray.indexingType(); + if (type != secondArray.indexingType()) + return NonArray; + if (type != ArrayWithDouble && type != ArrayWithInt32 && type != ArrayWithContiguous) + return NonArray; + if (firstArray.structure(vm)->holesMustForwardToPrototype(vm) + || secondArray.structure(vm)->holesMustForwardToPrototype(vm)) + return NonArray; + return type; } + EncodedJSValue fastConcatWith(ExecState&, JSArray&); + + enum ShiftCountMode { + // This form of shift hints that we're doing queueing. With this assumption in hand, + // we convert to ArrayStorage, which has queue optimizations. + ShiftCountForShift, + + // This form of shift hints that we're just doing care and feeding on an array that + // is probably typically used for ordinary accesses. With this assumption in hand, + // we try to preserve whatever indexing type it has already. + ShiftCountForSplice + }; - inline JSArray* asArray(JSValue value) + bool shiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count) { - return asArray(value.asCell()); + return shiftCountWithArrayStorage(exec->vm(), startIndex, count, ensureArrayStorage(exec->vm())); } - - inline bool isJSArray(JSGlobalData* globalData, JSValue v) + bool shiftCountForSplice(ExecState* exec, unsigned& startIndex, unsigned count) { - return v.isCell() && v.asCell()->vptr() == globalData->jsArrayVPtr; + return shiftCountWithAnyIndexingType(exec, startIndex, count); } - inline bool isJSArray(JSGlobalData* globalData, JSCell* cell) { return cell->vptr() == globalData->jsArrayVPtr; } - - inline void JSArray::markChildrenDirect(MarkStack& markStack) + template + bool shiftCount(ExecState* exec, unsigned& startIndex, unsigned count) { - JSObject::markChildrenDirect(markStack); + switch (shiftCountMode) { + case ShiftCountForShift: + return shiftCountForShift(exec, startIndex, count); + case ShiftCountForSplice: + return shiftCountForSplice(exec, startIndex, count); + default: + CRASH(); + return false; + } + } - ArrayStorage* storage = m_storage; + bool unshiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count) + { + return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm())); + } + bool unshiftCountForSplice(ExecState* exec, unsigned startIndex, unsigned count) + { + return unshiftCountWithAnyIndexingType(exec, startIndex, count); + } + template + bool unshiftCount(ExecState* exec, unsigned startIndex, unsigned count) + { + switch (shiftCountMode) { + case ShiftCountForShift: + return unshiftCountForShift(exec, startIndex, count); + case ShiftCountForSplice: + return unshiftCountForSplice(exec, startIndex, count); + default: + CRASH(); + return false; + } + } - unsigned usedVectorLength = std::min(storage->m_length, m_vectorLength); - markStack.appendValues(storage->m_vector, usedVectorLength, MayContainNullValues); + JS_EXPORT_PRIVATE void fillArgList(ExecState*, MarkedArgumentBuffer&); + JS_EXPORT_PRIVATE void copyToArguments(ExecState*, VirtualRegister firstElementDest, unsigned offset, unsigned length); - if (SparseArrayValueMap* map = storage->m_sparseValueMap) { - SparseArrayValueMap::iterator end = map->end(); - for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) - markStack.append(it->second); - } + static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype, IndexingType indexingType) + { + return Structure::create(vm, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), info(), indexingType); } + +protected: + static void put(JSCell*, ExecState*, PropertyName, JSValue, PutPropertySlot&); + + static bool deleteProperty(JSCell*, ExecState*, PropertyName); + JS_EXPORT_PRIVATE static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode); - inline void MarkStack::markChildren(JSCell* cell) +private: + bool isLengthWritable() { - ASSERT(Heap::isCellMarked(cell)); - if (!cell->structure()->typeInfo().overridesMarkChildren()) { -#ifdef NDEBUG - asObject(cell)->markChildrenDirect(*this); -#else - ASSERT(!m_isCheckingForDefaultMarkViolation); - m_isCheckingForDefaultMarkViolation = true; - cell->markChildren(*this); - ASSERT(m_isCheckingForDefaultMarkViolation); - m_isCheckingForDefaultMarkViolation = false; -#endif - return; - } - if (cell->vptr() == m_jsArrayVPtr) { - asArray(cell)->markChildrenDirect(*this); - return; + ArrayStorage* storage = arrayStorageOrNull(); + if (!storage) + return true; + SparseArrayValueMap* map = storage->m_sparseMap.get(); + return !map || !map->lengthIsReadOnly(); + } + + bool shiftCountWithAnyIndexingType(ExecState*, unsigned& startIndex, unsigned count); + JS_EXPORT_PRIVATE bool shiftCountWithArrayStorage(VM&, unsigned startIndex, unsigned count, ArrayStorage*); + + bool unshiftCountWithAnyIndexingType(ExecState*, unsigned startIndex, unsigned count); + bool unshiftCountWithArrayStorage(ExecState*, unsigned startIndex, unsigned count, ArrayStorage*); + bool unshiftCountSlowCase(VM&, bool, unsigned); + + bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*); + void setLengthWritable(ExecState*, bool writable); +}; + +inline Butterfly* createContiguousArrayButterfly(VM& vm, JSCell* intendedOwner, unsigned length, unsigned& vectorLength) +{ + IndexingHeader header; + vectorLength = std::max(length, BASE_VECTOR_LEN); + header.setVectorLength(vectorLength); + header.setPublicLength(length); + Butterfly* result = Butterfly::create( + vm, intendedOwner, 0, 0, true, header, vectorLength * sizeof(EncodedJSValue)); + return result; +} + +inline Butterfly* createArrayButterfly(VM& vm, JSCell* intendedOwner, unsigned initialLength) +{ + Butterfly* butterfly = Butterfly::create( + vm, intendedOwner, 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; + return butterfly; +} + +Butterfly* createArrayButterflyInDictionaryIndexingMode( + VM&, JSCell* intendedOwner, unsigned initialLength); + +inline JSArray* JSArray::create(VM& vm, Structure* structure, unsigned initialLength) +{ + Butterfly* butterfly; + if (LIKELY(!hasAnyArrayStorage(structure->indexingType()))) { + ASSERT( + hasUndecided(structure->indexingType()) + || hasInt32(structure->indexingType()) + || hasDouble(structure->indexingType()) + || hasContiguous(structure->indexingType())); + unsigned vectorLength; + butterfly = createContiguousArrayButterfly(vm, 0, initialLength, vectorLength); + ASSERT(initialLength < MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH); + if (hasDouble(structure->indexingType())) { + for (unsigned i = 0; i < vectorLength; ++i) + butterfly->contiguousDouble()[i] = PNaN; } - cell->markChildren(*this); + } else { + ASSERT( + structure->indexingType() == ArrayWithSlowPutArrayStorage + || structure->indexingType() == ArrayWithArrayStorage); + butterfly = createArrayButterfly(vm, 0, initialLength); } - inline void MarkStack::drain() - { - while (!m_markSets.isEmpty() || !m_values.isEmpty()) { - while (!m_markSets.isEmpty() && m_values.size() < 50) { - ASSERT(!m_markSets.isEmpty()); - MarkSet& current = m_markSets.last(); - ASSERT(current.m_values); - JSValue* end = current.m_end; - ASSERT(current.m_values); - ASSERT(current.m_values != end); - findNextUnmarkedNullValue: - ASSERT(current.m_values != end); - JSValue value = *current.m_values; - current.m_values++; - - JSCell* cell; - if (!value || !value.isCell() || Heap::isCellMarked(cell = value.asCell())) { - if (current.m_values == end) { - m_markSets.removeLast(); - continue; - } - goto findNextUnmarkedNullValue; - } - - Heap::markCell(cell); - if (cell->structure()->typeInfo().type() < CompoundType) { - if (current.m_values == end) { - m_markSets.removeLast(); - continue; - } - goto findNextUnmarkedNullValue; - } - - if (current.m_values == end) - m_markSets.removeLast(); - - markChildren(cell); - } - while (!m_values.isEmpty()) - markChildren(m_values.removeLast()); + return createWithButterfly(vm, structure, butterfly); +} + +inline JSArray* JSArray::tryCreateUninitialized(VM& vm, Structure* structure, unsigned initialLength) +{ + unsigned vectorLength = std::max(BASE_VECTOR_LEN, initialLength); + if (vectorLength > MAX_STORAGE_VECTOR_LENGTH) + return 0; + + Butterfly* butterfly; + if (LIKELY(!hasAnyArrayStorage(structure->indexingType()))) { + ASSERT( + hasUndecided(structure->indexingType()) + || hasInt32(structure->indexingType()) + || hasDouble(structure->indexingType()) + || hasContiguous(structure->indexingType())); + + void* temp; + if (!vm.heap.tryAllocateStorage(0, Butterfly::totalSize(0, 0, true, vectorLength * sizeof(EncodedJSValue)), &temp)) + return 0; + butterfly = Butterfly::fromBase(temp, 0, 0); + butterfly->setVectorLength(vectorLength); + butterfly->setPublicLength(initialLength); + if (hasDouble(structure->indexingType())) { + for (unsigned i = initialLength; i < vectorLength; ++i) + butterfly->contiguousDouble()[i] = PNaN; } + } else { + void* temp; + if (!vm.heap.tryAllocateStorage(0, Butterfly::totalSize(0, 0, true, ArrayStorage::sizeFor(vectorLength)), &temp)) + return 0; + 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; } + + return createWithButterfly(vm, structure, butterfly); +} + +inline JSArray* JSArray::createWithButterfly(VM& vm, Structure* structure, Butterfly* butterfly) +{ + JSArray* array = new (NotNull, allocateCell(vm.heap)) JSArray(vm, structure, butterfly); + array->finishCreation(vm); + return array; +} + +JSArray* asArray(JSValue); + +inline JSArray* asArray(JSCell* cell) +{ + ASSERT(cell->inherits(JSArray::info())); + return jsCast(cell); +} + +inline JSArray* asArray(JSValue value) +{ + return asArray(value.asCell()); +} + +inline bool isJSArray(JSCell* cell) { return cell->classInfo() == JSArray::info(); } +inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); } + +inline JSArray* constructArray(ExecState* exec, Structure* arrayStructure, const ArgList& values) +{ + VM& vm = exec->vm(); + unsigned length = values.size(); + JSArray* array = JSArray::tryCreateUninitialized(vm, arrayStructure, length); + + // FIXME: we should probably throw an out of memory error here, but + // when making this change we should check that all clients of this + // function will correctly handle an exception being thrown from here. + RELEASE_ASSERT(array); + + for (unsigned i = 0; i < length; ++i) + array->initializeIndex(vm, i, values.at(i)); + return array; +} +inline JSArray* constructArray(ExecState* exec, Structure* arrayStructure, const JSValue* values, unsigned length) +{ + VM& vm = exec->vm(); + JSArray* array = JSArray::tryCreateUninitialized(vm, arrayStructure, length); + + // FIXME: we should probably throw an out of memory error here, but + // when making this change we should check that all clients of this + // function will correctly handle an exception being thrown from here. + RELEASE_ASSERT(array); + + for (unsigned i = 0; i < length; ++i) + array->initializeIndex(vm, i, values[i]); + return array; +} + +inline JSArray* constructArrayNegativeIndexed(ExecState* exec, Structure* arrayStructure, const JSValue* values, unsigned length) +{ + VM& vm = exec->vm(); + JSArray* array = JSArray::tryCreateUninitialized(vm, arrayStructure, length); + + // FIXME: we should probably throw an out of memory error here, but + // when making this change we should check that all clients of this + // function will correctly handle an exception being thrown from here. + RELEASE_ASSERT(array); + + for (int i = 0; i < static_cast(length); ++i) + array->initializeIndex(vm, i, values[-i]); + return array; +} + } // namespace JSC #endif // JSArray_h