X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/ba379fdc102753d6be2c4d937058fe40257329fe..2d39b0e377c0896910ee49ae70082ba665faf986:/runtime/JSArray.h diff --git a/runtime/JSArray.h b/runtime/JSArray.h index ea490d8..d1366cf 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 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,109 +21,319 @@ #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_vectorLength; - unsigned m_numValuesInVector; - SparseArrayValueMap* m_sparseValueMap; - void* lazyCreationData; // A JSArray subclass can use this to fill the vector lazily. - JSValue m_vector[1]; - }; +class JSArray : public JSNonFinalObject { + friend class LLIntOffsetsExtractor; + friend class Walker; + friend class JIT; - class JSArray : public JSObject { - friend class JIT; +public: + typedef JSNonFinalObject Base; - public: - explicit JSArray(PassRefPtr); - JSArray(PassRefPtr, unsigned initialLength); - JSArray(PassRefPtr, const ArgList& initialValues); - virtual ~JSArray(); + static size_t allocationSize(size_t inlineCapacity) + { + ASSERT_UNUSED(inlineCapacity, !inlineCapacity); + return sizeof(JSArray); + } + +protected: + explicit JSArray(VM& vm, Structure* structure, Butterfly* butterfly) + : JSNonFinalObject(vm, structure, butterfly) + { + } - virtual bool getOwnPropertySlot(ExecState*, const Identifier& propertyName, PropertySlot&); - virtual bool getOwnPropertySlot(ExecState*, unsigned propertyName, PropertySlot&); - virtual void put(ExecState*, unsigned propertyName, JSValue); // FIXME: Make protected and add setItem. +public: + static JSArray* create(VM&, Structure*, unsigned initialLength = 0); - static JS_EXPORTDATA const ClassInfo info; + // 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); - 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. + JS_EXPORT_PRIVATE static bool defineOwnProperty(JSObject*, ExecState*, PropertyName, const PropertyDescriptor&, bool throwException); - void sort(ExecState*); - void sort(ExecState*, JSValue compareFunction, CallType, const CallData&); - void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&); + static bool getOwnPropertySlot(JSObject*, ExecState*, PropertyName, PropertySlot&); - void push(ExecState*, JSValue); - JSValue pop(); + DECLARE_EXPORT_INFO; + + 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); - bool canGetIndex(unsigned i) { return i < m_fastAccessCutoff; } - JSValue getIndex(unsigned i) - { - ASSERT(canGetIndex(i)); - return m_storage->m_vector[i]; - } + void sort(ExecState*); + void sort(ExecState*, JSValue compareFunction, CallType, const CallData&); + void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&); - bool canSetIndex(unsigned i) { return i < m_fastAccessCutoff; } - JSValue setIndex(unsigned i, JSValue v) - { - ASSERT(canSetIndex(i)); - return m_storage->m_vector[i] = v; - } + void push(ExecState*, JSValue); + JSValue pop(ExecState*); - void fillArgList(ExecState*, MarkedArgumentBuffer&); - void copyToRegisters(ExecState*, Register*, uint32_t); + 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 + }; - static PassRefPtr createStructure(JSValue prototype) - { - return Structure::create(prototype, TypeInfo(ObjectType)); + bool shiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count) + { + return shiftCountWithArrayStorage(exec->vm(), startIndex, count, ensureArrayStorage(exec->vm())); + } + bool shiftCountForSplice(ExecState* exec, unsigned& startIndex, unsigned count) + { + return shiftCountWithAnyIndexingType(exec, startIndex, count); + } + 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 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; + } + } - protected: - virtual void put(ExecState*, const Identifier& propertyName, JSValue, PutPropertySlot&); - virtual bool deleteProperty(ExecState*, const Identifier& propertyName); - virtual bool deleteProperty(ExecState*, unsigned propertyName); - virtual void getPropertyNames(ExecState*, PropertyNameArray&); - virtual void mark(); + void fillArgList(ExecState*, MarkedArgumentBuffer&); + void copyToArguments(ExecState*, CallFrame*, uint32_t length, int32_t firstVarArgOffset); - void* lazyCreationData(); - void setLazyCreationData(void*); + static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype, IndexingType indexingType) + { + return Structure::create(vm, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), info(), indexingType); + } + +protected: + static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesGetPropertyNames | JSObject::StructureFlags; + static void put(JSCell*, ExecState*, PropertyName, JSValue, PutPropertySlot&); - private: - virtual const ClassInfo* classInfo() const { return &info; } + static bool deleteProperty(JSCell*, ExecState*, PropertyName); + JS_EXPORT_PRIVATE static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode); - bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&); - void putSlowCase(ExecState*, unsigned propertyName, JSValue); +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(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 increaseVectorLength(unsigned newLength); + template + void sortNumericVector(ExecState*, JSValue compareFunction, CallType, const CallData&); - unsigned compactForSorting(); + template + void sortCompactedVector(ExecState*, ContiguousData, unsigned relevantLength); + + template + void sortVector(ExecState*, JSValue compareFunction, CallType, const CallData&); - enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck }; - void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck); + bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*); + void setLengthWritable(ExecState*, bool writable); + + template + void compactForSorting(unsigned& numDefined, unsigned& newRelevantLength); +}; - unsigned m_fastAccessCutoff; - ArrayStorage* m_storage; - }; +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; +} - JSArray* asArray(JSValue); +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; +} - JSArray* constructEmptyArray(ExecState*); - JSArray* constructEmptyArray(ExecState*, unsigned initialLength); - JSArray* constructArray(ExecState*, JSValue singleItemValue); - JSArray* constructArray(ExecState*, const ArgList& values); +Butterfly* createArrayButterflyInDictionaryIndexingMode( + VM&, JSCell* intendedOwner, unsigned initialLength); - inline JSArray* asArray(JSValue value) - { - ASSERT(asObject(value)->inherits(&JSArray::info)); - return static_cast(asObject(value)); +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_SPARSE_ARRAY_INDEX); + if (hasDouble(structure->indexingType())) { + for (unsigned i = 0; i < vectorLength; ++i) + butterfly->contiguousDouble()[i] = PNaN; + } + } else { + ASSERT( + structure->indexingType() == ArrayWithSlowPutArrayStorage + || structure->indexingType() == ArrayWithArrayStorage); + butterfly = createArrayButterfly(vm, 0, initialLength); + } + 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(!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; } + + 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); - inline bool isJSArray(JSGlobalData* globalData, JSValue v) { return v.isCell() && v.asCell()->vptr() == globalData->jsArrayVPtr; } + for (int i = 0; i < static_cast(length); ++i) + array->initializeIndex(vm, i, values[-i]); + return array; +} } // namespace JSC