Imported WebKit commit 2ea9d364d0f6efa8fa64acf19f451504c59be0e4 (http://svn.webkit.org/repository/webkit/trunk@104285)

1 files changed, 293 insertions, 0 deletions

diff --git a/Source/JavaScriptCore/runtime/JSArray.h b/Source/JavaScriptCore/runtime/JSArray.h
new file mode 100644
index 000000000..9102c8724
--- /dev/null
+++ b/Source/JavaScriptCore/runtime/JSArray.h
@@ -0,0 +1,293 @@
+/*
+ *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
+ *  Copyright (C) 2003, 2007, 2008, 2009 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
+ *  License as published by the Free Software Foundation; either
+ *  version 2 of the License, or (at your option) any later version.
+ *
+ *  This library is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  Lesser General Public License for more details.
+ *
+ *  You should have received a copy of the GNU Lesser General Public
+ *  License along with this library; if not, write to the Free Software
+ *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ */
+
+#ifndef JSArray_h
+#define JSArray_h
+
+#include "JSObject.h"
+
+#define CHECK_ARRAY_CONSISTENCY 0
+
+namespace JSC {
+
+    class JSArray;
+
+    struct SparseArrayEntry : public WriteBarrier<Unknown> {
+        SparseArrayEntry() : attributes(0) {}
+        unsigned attributes;
+    };
+
+    class SparseArrayValueMap {
+        typedef HashMap<unsigned, SparseArrayEntry> Map;
+
+        enum Flags {
+            Normal = 0,
+            SparseMode = 1
+        };
+
+    public:
+        typedef Map::iterator iterator;
+        typedef Map::const_iterator const_iterator;
+
+        SparseArrayValueMap()
+            : m_flags(Normal)
+            , m_reportedCapacity(0)
+        {
+        }
+
+        void visitChildren(SlotVisitor&);
+
+        bool sparseMode()
+        {
+            return m_flags & SparseMode;
+        }
+
+        void setSparseMode()
+        {
+            m_flags = (Flags)(m_flags | SparseMode);
+        }
+
+        // These methods may mutate the contents of the map
+        void put(JSGlobalData&, JSArray*, unsigned, JSValue);
+        iterator find(unsigned);
+        // This should ASSERT the remove is valid (check the result of the find).
+        void remove(iterator it) { m_map.remove(it); }
+        void remove(unsigned i) { m_map.remove(i); }
+
+        // These methods do not mutate the contents of the map.
+        iterator notFound() { return m_map.end(); }
+        bool isEmpty() const { return m_map.isEmpty(); }
+        bool contains(unsigned i) const { return m_map.contains(i); }
+        size_t size() const { return m_map.size(); }
+        // Only allow const begin/end iteration.
+        const_iterator begin() const { return m_map.begin(); }
+        const_iterator end() const { return m_map.end(); }
+
+    private:
+        Map m_map;
+        Flags m_flags;
+        size_t m_reportedCapacity;
+    };
+
+    // This struct holds the actual data values of an array.  A JSArray object points to it's contained ArrayStorage
+    // struct by pointing to m_vector.  To access the contained ArrayStorage struct, use the getStorage() and 
+    // setStorage() methods.  It is important to note that there may be space before the ArrayStorage that 
+    // is used to quick unshift / shift operation.  The actual allocated pointer is available by using:
+    //     getStorage() - m_indexBias * sizeof(JSValue)
+    struct ArrayStorage {
+        unsigned m_length; // The "length" property on the array
+        unsigned m_numValuesInVector;
+        SparseArrayValueMap* m_sparseValueMap;
+        void* subclassData; // A JSArray subclass can use this to fill the vector lazily.
+        void* m_allocBase; // Pointer to base address returned by malloc().  Keeping this pointer does eliminate false positives from the leak detector.
+#if CHECK_ARRAY_CONSISTENCY
+        bool m_inCompactInitialization;
+#endif
+        WriteBarrier<Unknown> m_vector[1];
+    };
+
+    class JSArray : public JSNonFinalObject {
+        friend class Walker;
+
+    protected:
+        explicit JSArray(JSGlobalData&, Structure*);
+
+        void finishCreation(JSGlobalData&, unsigned initialLength = 0);
+        JSArray* tryFinishCreationUninitialized(JSGlobalData&, unsigned initialLength);
+    
+    public:
+        typedef JSNonFinalObject Base;
+
+        ~JSArray();
+        static void destroy(JSCell*);
+
+        static JSArray* create(JSGlobalData& globalData, Structure* structure, unsigned initialLength = 0)
+        {
+            JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
+            array->finishCreation(globalData, initialLength);
+            return array;
+        }
+
+        // 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.
+        //   - called 'completeInitialization' after all properties have been initialized.
+        static JSArray* tryCreateUninitialized(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
+        {
+            JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
+            return array->tryFinishCreationUninitialized(globalData, initialLength);
+        }
+
+        static bool getOwnPropertySlot(JSCell*, ExecState*, const Identifier& propertyName, PropertySlot&);
+        static bool getOwnPropertySlotByIndex(JSCell*, ExecState*, unsigned propertyName, PropertySlot&);
+        static bool getOwnPropertyDescriptor(JSObject*, ExecState*, const Identifier&, PropertyDescriptor&);
+        static void putByIndex(JSCell*, ExecState*, unsigned propertyName, JSValue);
+
+        static JS_EXPORTDATA const ClassInfo s_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();
+
+        void shiftCount(ExecState*, unsigned count);
+        void unshiftCount(ExecState*, unsigned count);
+
+        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].get();
+        }
+
+        bool canSetIndex(unsigned i) { return i < m_vectorLength; }
+        void setIndex(JSGlobalData& globalData, unsigned i, JSValue v)
+        {
+            ASSERT(canSetIndex(i));
+            
+            WriteBarrier<Unknown>& x = m_storage->m_vector[i];
+            if (!x) {
+                ArrayStorage *storage = m_storage;
+                ++storage->m_numValuesInVector;
+                if (i >= storage->m_length)
+                    storage->m_length = i + 1;
+            }
+            x.set(globalData, this, v);
+        }
+        
+        inline void initializeIndex(JSGlobalData& globalData, unsigned i, JSValue v)
+        {
+            ASSERT(canSetIndex(i));
+            ArrayStorage *storage = m_storage;
+#if CHECK_ARRAY_CONSISTENCY
+            ASSERT(storage->m_inCompactInitialization);
+#endif
+            // Check that we are initializing the next index in sequence.
+            ASSERT_UNUSED(i, i == storage->m_length);
+            // tryCreateUninitialized set m_numValuesInVector to the initialLength,
+            // check we do not try to initialize more than this number of properties.
+            ASSERT(storage->m_length < storage->m_numValuesInVector);
+            // It is improtant that we increment length here, so that all newly added
+            // values in the array still get marked during the initialization phase.
+            storage->m_vector[storage->m_length++].set(globalData, this, v);
+        }
+
+        inline void completeInitialization(unsigned newLength)
+        {
+            // Check that we have initialized as meny properties as we think we have.
+            ASSERT_UNUSED(newLength, newLength == m_storage->m_length);
+            // Check that the number of propreties initialized matches the initialLength.
+            ASSERT(m_storage->m_length == m_storage->m_numValuesInVector);
+#if CHECK_ARRAY_CONSISTENCY
+            ASSERT(m_storage->m_inCompactInitialization);
+            m_storage->m_inCompactInitialization = false;
+#endif
+        }
+
+        bool inSparseMode()
+        {
+            SparseArrayValueMap* map = m_storage->m_sparseValueMap;
+            return map && map->sparseMode();
+        }
+
+        void fillArgList(ExecState*, MarkedArgumentBuffer&);
+        void copyToArguments(ExecState*, CallFrame*, uint32_t length);
+
+        static Structure* createStructure(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype)
+        {
+            return Structure::create(globalData, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), &s_info);
+        }
+        
+        static ptrdiff_t storageOffset()
+        {
+            return OBJECT_OFFSETOF(JSArray, m_storage);
+        }
+
+        static ptrdiff_t vectorLengthOffset()
+        {
+            return OBJECT_OFFSETOF(JSArray, m_vectorLength);
+        }
+
+        static void visitChildren(JSCell*, SlotVisitor&);
+
+    protected:
+        static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesVisitChildren | OverridesGetPropertyNames | JSObject::StructureFlags;
+        static void put(JSCell*, ExecState*, const Identifier& propertyName, JSValue, PutPropertySlot&);
+
+        static bool deleteProperty(JSCell*, ExecState*, const Identifier& propertyName);
+        static bool deletePropertyByIndex(JSCell*, ExecState*, unsigned propertyName);
+        static void getOwnPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
+
+        void* subclassData() const;
+        void setSubclassData(void*);
+
+    private:
+        bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&);
+        void putByIndexBeyondVectorLength(JSGlobalData&, unsigned propertyName, JSValue);
+
+        unsigned getNewVectorLength(unsigned desiredLength);
+        bool increaseVectorLength(unsigned newLength);
+        bool unshiftCountSlowCase(unsigned count);
+        
+        unsigned compactForSorting();
+
+        enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck };
+        void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck);
+
+        unsigned m_vectorLength; // The valid length of m_vector
+        unsigned m_indexBias; // The number of JSValue sized blocks before ArrayStorage.
+        ArrayStorage *m_storage;
+    };
+
+    JSArray* asArray(JSValue);
+
+    inline JSArray* asArray(JSCell* cell)
+    {
+        ASSERT(cell->inherits(&JSArray::s_info));
+        return static_cast<JSArray*>(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()); }
+
+    // Rule from ECMA 15.2 about what an array index is.
+    // Must exactly match string form of an unsigned integer, and be less than 2^32 - 1.
+    inline unsigned Identifier::toArrayIndex(bool& ok) const
+    {
+        unsigned i = toUInt32(ok);
+        if (ok && i >= 0xFFFFFFFFU)
+            ok = false;
+        return i;
+    }
+
+} // namespace JSC
+
+#endif // JSArray_h