JavaScriptCore-7600.1.4.16.1.tar.gz

[apple/javascriptcore.git] / runtime / JSArray.h

diff --git a/runtime/JSArray.h b/runtime/JSArray.h
index ad6ee88c92e0bb504652cd81e7d248548c7eb89b..d1366cff2556cc503961bf4113f8f019db207159 100644 (file)
--- a/runtime/JSArray.h
+++ b/runtime/JSArray.h
@@ -1,6 +1,6 @@
 /*
  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
 /*
  *  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
  *
  *  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,320 @@
 #ifndef JSArray_h
 #define JSArray_h
 
 #ifndef JSArray_h
 #define JSArray_h
 

+#include "ArrayConventions.h"
+#include "ButterflyInlines.h"

 #include "JSObject.h"
 
 namespace JSC {
 
 #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
 } // namespace JSC
 
 #endif // JSArray_h