X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/f9bf01c6616d5ddcf65b13b33cedf9e387ff7a63..4be4e30906bcb8ee30b4d189205cb70bad6707ce:/runtime/JSArray.h diff --git a/runtime/JSArray.h b/runtime/JSArray.h index ad6ee88..af81d2e 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 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,298 @@ #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&); +class JSArray : public JSNonFinalObject { + friend class LLIntOffsetsExtractor; + friend class Walker; + friend class JIT; - void push(ExecState*, JSValue); - JSValue pop(); +public: + typedef JSNonFinalObject Base; - 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; - } - - void fillArgList(ExecState*, MarkedArgumentBuffer&); - void copyToRegisters(ExecState*, Register*, uint32_t); - - static PassRefPtr createStructure(JSValue prototype) - { - return Structure::create(prototype, TypeInfo(ObjectType, StructureFlags), AnonymousSlotCount); - } - - 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); - 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, PropertyDescriptor&, bool throwException); - bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&); - void putSlowCase(ExecState*, unsigned propertyName, JSValue); + static bool getOwnPropertySlot(JSCell*, ExecState*, PropertyName, PropertySlot&); + static bool getOwnPropertyDescriptor(JSObject*, ExecState*, PropertyName, PropertyDescriptor&); - bool increaseVectorLength(unsigned newLength); + static JS_EXPORTDATA const ClassInfo s_info; - unsigned compactForSorting(); - - enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck }; - void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck); - - unsigned m_vectorLength; - ArrayStorage* m_storage; + 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); + + 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(ExecState*); + + 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 }; - JSArray* asArray(JSValue); - - inline JSArray* asArray(JSCell* cell) + bool shiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count) { - ASSERT(cell->inherits(&JSArray::info)); - return static_cast(cell); + return shiftCountWithArrayStorage(startIndex, count, ensureArrayStorage(exec->vm())); } - - inline JSArray* asArray(JSValue value) + bool shiftCountForSplice(ExecState* exec, unsigned startIndex, unsigned count) { - return asArray(value.asCell()); + return shiftCountWithAnyIndexingType(exec, startIndex, count); } - - inline bool isJSArray(JSGlobalData* globalData, JSValue v) + template + bool shiftCount(ExecState* exec, unsigned startIndex, unsigned count) + { + switch (shiftCountMode) { + case ShiftCountForShift: + return shiftCountForShift(exec, startIndex, count); + case ShiftCountForSplice: + return shiftCountForSplice(exec, startIndex, count); + default: + CRASH(); + return false; + } + } + + bool unshiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count) { - return v.isCell() && v.asCell()->vptr() == globalData->jsArrayVPtr; + return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm())); } - inline bool isJSArray(JSGlobalData* globalData, JSCell* cell) { return cell->vptr() == globalData->jsArrayVPtr; } + 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; + } + } + + void fillArgList(ExecState*, MarkedArgumentBuffer&); + void copyToArguments(ExecState*, CallFrame*, uint32_t length); - inline void JSArray::markChildrenDirect(MarkStack& markStack) + static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype, IndexingType indexingType) { - JSObject::markChildrenDirect(markStack); + return Structure::create(vm, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), &s_info, indexingType); + } - ArrayStorage* storage = m_storage; +protected: + static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesGetPropertyNames | JSObject::StructureFlags; + static void put(JSCell*, ExecState*, PropertyName, JSValue, PutPropertySlot&); - unsigned usedVectorLength = std::min(storage->m_length, m_vectorLength); - markStack.appendValues(storage->m_vector, usedVectorLength, MayContainNullValues); + static bool deleteProperty(JSCell*, ExecState*, PropertyName); + JS_EXPORT_PRIVATE static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode); - if (SparseArrayValueMap* map = storage->m_sparseValueMap) { - SparseArrayValueMap::iterator end = map->end(); - for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) - markStack.append(it->second); - } +private: + bool isLengthWritable() + { + ArrayStorage* storage = arrayStorageOrNull(); + if (!storage) + return true; + SparseArrayValueMap* map = storage->m_sparseMap.get(); + return !map || !map->lengthIsReadOnly(); } + + bool shiftCountWithAnyIndexingType(ExecState*, unsigned startIndex, unsigned count); + bool shiftCountWithArrayStorage(unsigned startIndex, unsigned count, ArrayStorage*); - inline void MarkStack::markChildren(JSCell* cell) - { - 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; + bool unshiftCountWithAnyIndexingType(ExecState*, unsigned startIndex, unsigned count); + bool unshiftCountWithArrayStorage(ExecState*, unsigned startIndex, unsigned count, ArrayStorage*); + bool unshiftCountSlowCase(VM&, bool, unsigned); + + template + void sortNumericVector(ExecState*, JSValue compareFunction, CallType, const CallData&); + + template + void sortCompactedVector(ExecState*, ContiguousData, unsigned relevantLength); + + template + void sortVector(ExecState*, JSValue compareFunction, CallType, const CallData&); + + bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*); + void setLengthWritable(ExecState*, bool writable); + + template + void compactForSorting(unsigned& numDefined, unsigned& newRelevantLength); +}; + +inline Butterfly* createContiguousArrayButterfly(VM& vm, unsigned length, unsigned& vectorLength) +{ + IndexingHeader header; + vectorLength = std::max(length, BASE_VECTOR_LEN); + header.setVectorLength(vectorLength); + header.setPublicLength(length); + Butterfly* result = Butterfly::create( + vm, 0, 0, true, header, vectorLength * sizeof(EncodedJSValue)); + return result; +} + +inline Butterfly* createArrayButterfly(VM& vm, unsigned initialLength) +{ + Butterfly* butterfly = Butterfly::create( + vm, 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&, unsigned initialLength); + +inline JSArray* JSArray::create(VM& vm, Structure* structure, unsigned initialLength) +{ + Butterfly* butterfly; + if (LIKELY(!hasArrayStorage(structure->indexingType()))) { + ASSERT( + hasUndecided(structure->indexingType()) + || hasInt32(structure->indexingType()) + || hasDouble(structure->indexingType()) + || hasContiguous(structure->indexingType())); + unsigned vectorLength; + butterfly = createContiguousArrayButterfly(vm, initialLength, vectorLength); + ASSERT(initialLength < MIN_SPARSE_ARRAY_INDEX); + if (hasDouble(structure->indexingType())) { + for (unsigned i = 0; i < vectorLength; ++i) + butterfly->contiguousDouble()[i] = QNaN; } - cell->markChildren(*this); + } else { + ASSERT( + structure->indexingType() == ArrayWithSlowPutArrayStorage + || structure->indexingType() == ArrayWithArrayStorage); + butterfly = createArrayButterfly(vm, 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()); + JSArray* array = new (NotNull, allocateCell(vm.heap)) JSArray(vm, structure, butterfly); + array->finishCreation(vm); + return array; +} + +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(!hasArrayStorage(structure->indexingType()))) { + ASSERT( + hasUndecided(structure->indexingType()) + || hasInt32(structure->indexingType()) + || hasDouble(structure->indexingType()) + || hasContiguous(structure->indexingType())); + + void* temp; + if (!vm.heap.tryAllocateStorage(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] = QNaN; } + } else { + void* temp; + if (!vm.heap.tryAllocateStorage(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; } + + 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::s_info)); + return jsCast(cell); +} + +inline JSArray* asArray(JSValue value) +{ + return asArray(value.asCell()); +} + +inline bool isJSArray(JSCell* cell) { return cell->classInfo() == &JSArray::s_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; +} + } // namespace JSC #endif // JSArray_h