/*
* 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
#ifndef JSArray_h
#define JSArray_h
+#include "ArrayConventions.h"
+#include "ButterflyInlines.h"
#include "JSObject.h"
namespace JSC {
- typedef HashMap<unsigned, JSValue> 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<Structure>);
- JSArray(NonNullPassRefPtr<Structure>, unsigned initialLength);
- JSArray(NonNullPassRefPtr<Structure>, 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 PassRefPtr<Structure> 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);
- 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);
+ static bool getOwnPropertySlot(JSObject*, ExecState*, PropertyName, PropertySlot&);
- bool increaseVectorLength(unsigned newLength);
+ DECLARE_EXPORT_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<JSArray*>(cell);
+ return shiftCountWithArrayStorage(exec->vm(), 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<ShiftCountMode shiftCountMode>
+ 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<ShiftCountMode shiftCountMode>
+ bool unshiftCount(ExecState* exec, unsigned startIndex, unsigned count)
{
- return v.isCell() && v.asCell()->vptr() == globalData->jsArrayVPtr;
+ switch (shiftCountMode) {
+ case ShiftCountForShift:
+ return unshiftCountForShift(exec, startIndex, count);
+ case ShiftCountForSplice:
+ return unshiftCountForSplice(exec, startIndex, count);
+ default:
+ CRASH();
+ return false;
+ }
}
- inline bool isJSArray(JSGlobalData* globalData, JSCell* cell) { return cell->vptr() == globalData->jsArrayVPtr; }
- inline void JSArray::markChildrenDirect(MarkStack& markStack)
+ void fillArgList(ExecState*, MarkedArgumentBuffer&);
+ void copyToArguments(ExecState*, CallFrame*, uint32_t length, int32_t firstVarArgOffset);
+
+ static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype, IndexingType indexingType)
{
- JSObject::markChildrenDirect(markStack);
+ return Structure::create(vm, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), 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(VM&, 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<IndexingType indexingType>
+ void sortNumericVector(ExecState*, JSValue compareFunction, CallType, const CallData&);
+
+ template<IndexingType indexingType, typename StorageType>
+ void sortCompactedVector(ExecState*, ContiguousData<StorageType>, unsigned relevantLength);
+
+ template<IndexingType indexingType>
+ void sortVector(ExecState*, JSValue compareFunction, CallType, const CallData&);
+
+ bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*);
+ void setLengthWritable(ExecState*, bool writable);
+
+ template<IndexingType indexingType>
+ void compactForSorting(unsigned& numDefined, unsigned& newRelevantLength);
+};
+
+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_SPARSE_ARRAY_INDEX);
+ 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());
+ JSArray* array = new (NotNull, allocateCell<JSArray>(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<JSArray>(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<JSArray*>(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<int>(length); ++i)
+ array->initializeIndex(vm, i, values[-i]);
+ return array;
+}
+
} // namespace JSC
#endif // JSArray_h
projects / apple / javascriptcore.git / blobdiff