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

/*
 *  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;
    class LLIntOffsetsExtractor;

    struct SparseArrayEntry : public WriteBarrier<Unknown> {
        typedef WriteBarrier<Unknown> Base;

        SparseArrayEntry() : attributes(0) {}

        JSValue get(ExecState*, JSArray*) const;
        void get(PropertySlot&) const;
        void get(PropertyDescriptor&) const;
        JSValue getNonSparseMode() const;

        unsigned attributes;
    };

    class SparseArrayValueMap {
        typedef HashMap<uint64_t, SparseArrayEntry, WTF::IntHash<uint64_t>, WTF::UnsignedWithZeroKeyHashTraits<uint64_t> > Map;

        enum Flags {
            Normal = 0,
            SparseMode = 1,
            LengthIsReadOnly = 2,
        };

    public:
        typedef Map::iterator iterator;
        typedef Map::const_iterator const_iterator;
        typedef Map::AddResult AddResult;

        SparseArrayValueMap()
            : m_flags(Normal)
            , m_reportedCapacity(0)
        {
        }

        void visitChildren(SlotVisitor&);

        bool sparseMode()
        {
            return m_flags & SparseMode;
        }

        void setSparseMode()
        {
            m_flags = static_cast<Flags>(m_flags | SparseMode);
        }

        bool lengthIsReadOnly()
        {
            return m_flags & LengthIsReadOnly;
        }

        void setLengthIsReadOnly()
        {
            m_flags = static_cast<Flags>(m_flags | LengthIsReadOnly);
        }

        // These methods may mutate the contents of the map
        void put(ExecState*, JSArray*, unsigned, JSValue, bool shouldThrow);
        bool putDirect(ExecState*, JSArray*, unsigned, JSValue, bool shouldThrow);
        AddResult add(JSArray*, unsigned);
        iterator find(unsigned i) { return m_map.find(i); }
        // 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;
        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
        // Needs to be a uintptr_t for alignment purposes.
        uintptr_t m_initializationIndex;
        uintptr_t m_inCompactInitialization;
#else
        uintptr_t m_padding;
#endif
        WriteBarrier<Unknown> m_vector[1];

        static ptrdiff_t lengthOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_length); }
        static ptrdiff_t numValuesInVectorOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_numValuesInVector); }
        static ptrdiff_t allocBaseOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_allocBase); }
        static ptrdiff_t vectorOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_vector); }
    };

    class JSArray : public JSNonFinalObject {
        friend class LLIntOffsetsExtractor;
        friend class Walker;
        friend class JIT;

    protected:
        explicit JSArray(JSGlobalData& globalData, Structure* structure)
            : JSNonFinalObject(globalData, structure)
            , m_indexBias(0)
            , m_storage(0)
            , m_sparseValueMap(0)
        {
        }

        JS_EXPORT_PRIVATE void finishCreation(JSGlobalData&, unsigned initialLength = 0);
        JS_EXPORT_PRIVATE JSArray* tryFinishCreationUninitialized(JSGlobalData&, unsigned initialLength);
    
    public:
        typedef JSNonFinalObject Base;

        static void finalize(JSCell*);

        static JSArray* create(JSGlobalData&, Structure*, unsigned initialLength = 0);

        // 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&, Structure*, unsigned initialLength);

        JS_EXPORT_PRIVATE static bool defineOwnProperty(JSObject*, ExecState*, const Identifier&, PropertyDescriptor&, bool throwException);

        static bool getOwnPropertySlot(JSCell*, ExecState*, const Identifier&, PropertySlot&);
        JS_EXPORT_PRIVATE static bool getOwnPropertySlotByIndex(JSCell*, ExecState*, unsigned propertyName, PropertySlot&);
        static bool getOwnPropertyDescriptor(JSObject*, ExecState*, const Identifier&, PropertyDescriptor&);
        static void putByIndex(JSCell*, ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
        // This is similar to the JSObject::putDirect* methods:
        //  - the prototype chain is not consulted
        //  - accessors are not called.
        // This method creates a property with attributes writable, enumerable and configurable all set to true.
        bool putDirectIndex(ExecState* exec, unsigned propertyName, JSValue value, bool shouldThrow = true)
        {
            if (canSetIndex(propertyName)) {
                setIndex(exec->globalData(), propertyName, value);
                return true;
            }
            return putDirectIndexBeyondVectorLength(exec, propertyName, value, shouldThrow);
        }

        static JS_EXPORTDATA const ClassInfo s_info;
        
        unsigned length() const { return m_storage->m_length; }
        // 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*);

        bool shiftCount(ExecState*, unsigned count);
        bool 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);
            // Check that we are initializing the next index in sequence.
            ASSERT(i == storage->m_initializationIndex);
            // tryCreateUninitialized set m_numValuesInVector to the initialLength,
            // check we do not try to initialize more than this number of properties.
            ASSERT(storage->m_initializationIndex < storage->m_numValuesInVector);
            storage->m_initializationIndex++;
#endif
            ASSERT(i < storage->m_length);
            ASSERT(i < storage->m_numValuesInVector);
            storage->m_vector[i].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);
#if CHECK_ARRAY_CONSISTENCY
            // Check that the number of propreties initialized matches the initialLength.
            ASSERT(m_storage->m_initializationIndex == m_storage->m_numValuesInVector);
            ASSERT(m_storage->m_inCompactInitialization);
            m_storage->m_inCompactInitialization = false;
#endif
        }

        bool inSparseMode()
        {
            SparseArrayValueMap* map = 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);
        }

        JS_EXPORT_PRIVATE static void visitChildren(JSCell*, SlotVisitor&);

        void enterDictionaryMode(JSGlobalData&);

    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);

        JS_EXPORT_PRIVATE void* subclassData() const;
        JS_EXPORT_PRIVATE void setSubclassData(void*);

    private:
        static size_t storageSize(unsigned vectorLength);
        bool isLengthWritable()
        {
            SparseArrayValueMap* map = m_sparseValueMap;
            return !map || !map->lengthIsReadOnly();
        }

        void setLengthWritable(ExecState*, bool writable);
        void putDescriptor(ExecState*, SparseArrayEntry*, PropertyDescriptor&, PropertyDescriptor& old);
        bool defineOwnNumericProperty(ExecState*, unsigned, PropertyDescriptor&, bool throwException);
        void allocateSparseMap(JSGlobalData&);
        void deallocateSparseMap();

        bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&);
        void putByIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
        JS_EXPORT_PRIVATE bool putDirectIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, bool shouldThrow);

        unsigned getNewVectorLength(unsigned desiredLength);
        bool increaseVectorLength(JSGlobalData&, unsigned newLength);
        bool unshiftCountSlowCase(JSGlobalData&, unsigned count);
        
        unsigned compactForSorting(JSGlobalData&);

        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;

        // FIXME: Maybe SparseArrayValueMap should be put into its own JSCell?
        SparseArrayValueMap* m_sparseValueMap;

        static ptrdiff_t sparseValueMapOffset() { return OBJECT_OFFSETOF(JSArray, m_sparseValueMap); }
        static ptrdiff_t indexBiasOffset() { return OBJECT_OFFSETOF(JSArray, m_indexBias); }
    };

    inline JSArray* JSArray::create(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
    {
        JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
        array->finishCreation(globalData, initialLength);
        return array;
    }

    inline JSArray* JSArray::tryCreateUninitialized(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
    {
        JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
        return array->tryFinishCreationUninitialized(globalData, initialLength);
    }

    JSArray* asArray(JSValue);

    inline JSArray* asArray(JSCell* cell)
    {
        ASSERT(cell->inherits(&JSArray::s_info));
        return jsCast<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;
    }

// The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
// function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
// size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) +
// (vectorLength * sizeof(WriteBarrier<Unknown>)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
#define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>))

// These values have to be macros to be used in max() and min() without introducing
// a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
#define MIN_SPARSE_ARRAY_INDEX 10000U
#define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
    inline size_t JSArray::storageSize(unsigned vectorLength)
    {
        ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH);
    
        // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH)
        // - as asserted above - the following calculation cannot overflow.
        size_t size = (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) + (vectorLength * sizeof(WriteBarrier<Unknown>));
        // Assertion to detect integer overflow in previous calculation (should not be possible, provided that
        // MAX_STORAGE_VECTOR_LENGTH is correctly defined).
        ASSERT(((size - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))));
    
        return size;
    }
    
    } // namespace JSC

#endif // JSArray_h
Commit	Line	Data
9dae56ea A	1	/*
9dae56ea A	2	* Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
f9bf01c6	3	* Copyright (C) 2003, 2007, 2008, 2009 Apple Inc. All rights reserved.
9dae56ea A	4	*
	5	* This library is free software; you can redistribute it and/or
	6	* modify it under the terms of the GNU Lesser General Public
	7	* License as published by the Free Software Foundation; either
	8	* version 2 of the License, or (at your option) any later version.
	9	*
	10	* This library is distributed in the hope that it will be useful,
	11	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	12	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	13	* Lesser General Public License for more details.
	14	*
	15	* You should have received a copy of the GNU Lesser General Public
	16	* License along with this library; if not, write to the Free Software
	17	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
	18	*
	19	*/
	20
	21	#ifndef JSArray_h
	22	#define JSArray_h
	23
	24	#include "JSObject.h"
	25
14957cd0 A	26	#define CHECK_ARRAY_CONSISTENCY 0
14957cd0 A	27
9dae56ea A	28	namespace JSC {
9dae56ea A	29
6fe7ccc8 A	30	class JSArray;
	31	class LLIntOffsetsExtractor;
	32
	33	struct SparseArrayEntry : public WriteBarrier<Unknown> {
	34	typedef WriteBarrier<Unknown> Base;
	35
	36	SparseArrayEntry() : attributes(0) {}
	37
	38	JSValue get(ExecState, JSArray) const;
	39	void get(PropertySlot&) const;
	40	void get(PropertyDescriptor&) const;
	41	JSValue getNonSparseMode() const;
	42
	43	unsigned attributes;
	44	};
	45
	46	class SparseArrayValueMap {
	47	typedef HashMap<uint64_t, SparseArrayEntry, WTF::IntHash<uint64_t>, WTF::UnsignedWithZeroKeyHashTraits<uint64_t> > Map;
	48
	49	enum Flags {
	50	Normal = 0,
	51	SparseMode = 1,
	52	LengthIsReadOnly = 2,
	53	};
	54
	55	public:
	56	typedef Map::iterator iterator;
	57	typedef Map::const_iterator const_iterator;
	58	typedef Map::AddResult AddResult;
	59
	60	SparseArrayValueMap()
	61	: m_flags(Normal)
	62	, m_reportedCapacity(0)
	63	{
	64	}
	65
	66	void visitChildren(SlotVisitor&);
	67
	68	bool sparseMode()
	69	{
	70	return m_flags & SparseMode;
	71	}
	72
	73	void setSparseMode()
	74	{
	75	m_flags = static_cast<Flags>(m_flags \| SparseMode);
	76	}
	77
	78	bool lengthIsReadOnly()
	79	{
	80	return m_flags & LengthIsReadOnly;
	81	}
	82
	83	void setLengthIsReadOnly()
	84	{
	85	m_flags = static_cast<Flags>(m_flags \| LengthIsReadOnly);
	86	}
	87
	88	// These methods may mutate the contents of the map
	89	void put(ExecState, JSArray, unsigned, JSValue, bool shouldThrow);
	90	bool putDirect(ExecState, JSArray, unsigned, JSValue, bool shouldThrow);
	91	AddResult add(JSArray*, unsigned);
	92	iterator find(unsigned i) { return m_map.find(i); }
	93	// This should ASSERT the remove is valid (check the result of the find).
94	void remove(iterator it) { m_map.remove(it); }
95	void remove(unsigned i) { m_map.remove(i); }
96
97	// These methods do not mutate the contents of the map.
98	iterator notFound() { return m_map.end(); }
99	bool isEmpty() const { return m_map.isEmpty(); }
100	bool contains(unsigned i) const { return m_map.contains(i); }
101	size_t size() const { return m_map.size(); }
102	// Only allow const begin/end iteration.
103	const_iterator begin() const { return m_map.begin(); }
104	const_iterator end() const { return m_map.end(); }
105
106	private:
107	Map m_map;
108	Flags m_flags;
109	size_t m_reportedCapacity;
110	};
9dae56ea	111
14957cd0 A	112	// This struct holds the actual data values of an array. A JSArray object points to it's contained ArrayStorage
	113	// struct by pointing to m_vector. To access the contained ArrayStorage struct, use the getStorage() and
	114	// setStorage() methods. It is important to note that there may be space before the ArrayStorage that
	115	// is used to quick unshift / shift operation. The actual allocated pointer is available by using:
	116	// getStorage() - m_indexBias * sizeof(JSValue)
9dae56ea	117	struct ArrayStorage {
14957cd0	118	unsigned m_length; // The "length" property on the array
9dae56ea	119	unsigned m_numValuesInVector;
14957cd0	120	void* m_allocBase; // Pointer to base address returned by malloc(). Keeping this pointer does eliminate false positives from the leak detector.
14957cd0	121	#if CHECK_ARRAY_CONSISTENCY
6fe7ccc8 A	122	// Needs to be a uintptr_t for alignment purposes.
	123	uintptr_t m_initializationIndex;
	124	uintptr_t m_inCompactInitialization;
	125	#else
	126	uintptr_t m_padding;
14957cd0 A	127	#endif
14957cd0 A	128	WriteBarrier<Unknown> m_vector[1];
14957cd0	129
6fe7ccc8 A	130	static ptrdiff_t lengthOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_length); }
	131	static ptrdiff_t numValuesInVectorOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_numValuesInVector); }
	132	static ptrdiff_t allocBaseOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_allocBase); }
	133	static ptrdiff_t vectorOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_vector); }
	134	};
14957cd0 A	135
14957cd0 A	136	class JSArray : public JSNonFinalObject {
6fe7ccc8	137	friend class LLIntOffsetsExtractor;
f9bf01c6	138	friend class Walker;
6fe7ccc8	139	friend class JIT;
9dae56ea	140
6fe7ccc8 A	141	protected:
	142	explicit JSArray(JSGlobalData& globalData, Structure* structure)
	143	: JSNonFinalObject(globalData, structure)
	144	, m_indexBias(0)
	145	, m_storage(0)
	146	, m_sparseValueMap(0)
	147	{
	148	}
9dae56ea	149
6fe7ccc8 A	150	JS_EXPORT_PRIVATE void finishCreation(JSGlobalData&, unsigned initialLength = 0);
	151	JS_EXPORT_PRIVATE JSArray* tryFinishCreationUninitialized(JSGlobalData&, unsigned initialLength);
	152
	153	public:
	154	typedef JSNonFinalObject Base;
	155
	156	static void finalize(JSCell*);
	157
	158	static JSArray* create(JSGlobalData&, Structure*, unsigned initialLength = 0);
	159
	160	// tryCreateUninitialized is used for fast construction of arrays whose size and
	161	// contents are known at time of creation. Clients of this interface must:
	162	// - null-check the result (indicating out of memory, or otherwise unable to allocate vector).
	163	// - call 'initializeIndex' for all properties in sequence, for 0 <= i < initialLength.
	164	// - called 'completeInitialization' after all properties have been initialized.
	165	static JSArray* tryCreateUninitialized(JSGlobalData&, Structure*, unsigned initialLength);
	166
	167	JS_EXPORT_PRIVATE static bool defineOwnProperty(JSObject, ExecState, const Identifier&, PropertyDescriptor&, bool throwException);
	168
	169	static bool getOwnPropertySlot(JSCell, ExecState, const Identifier&, PropertySlot&);
	170	JS_EXPORT_PRIVATE static bool getOwnPropertySlotByIndex(JSCell, ExecState, unsigned propertyName, PropertySlot&);
	171	static bool getOwnPropertyDescriptor(JSObject, ExecState, const Identifier&, PropertyDescriptor&);
	172	static void putByIndex(JSCell, ExecState, unsigned propertyName, JSValue, bool shouldThrow);
	173	// This is similar to the JSObject::putDirect* methods:
	174	// - the prototype chain is not consulted
	175	// - accessors are not called.
	176	// This method creates a property with attributes writable, enumerable and configurable all set to true.
	177	bool putDirectIndex(ExecState* exec, unsigned propertyName, JSValue value, bool shouldThrow = true)
	178	{
	179	if (canSetIndex(propertyName)) {
	180	setIndex(exec->globalData(), propertyName, value);
	181	return true;
	182	}
	183	return putDirectIndexBeyondVectorLength(exec, propertyName, value, shouldThrow);
	184	}
9dae56ea	185
14957cd0 A	186	static JS_EXPORTDATA const ClassInfo s_info;
14957cd0 A	187
9dae56ea	188	unsigned length() const { return m_storage->m_length; }
6fe7ccc8 A	189	// OK to use on new arrays, but not if it might be a RegExpMatchArray.
6fe7ccc8 A	190	bool setLength(ExecState*, unsigned, bool throwException = false);
9dae56ea A	191
9dae56ea A	192	void sort(ExecState*);
ba379fdc A	193	void sort(ExecState*, JSValue compareFunction, CallType, const CallData&);
ba379fdc A	194	void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&);
9dae56ea	195
ba379fdc	196	void push(ExecState*, JSValue);
6fe7ccc8	197	JSValue pop(ExecState*);
9dae56ea	198
6fe7ccc8 A	199	bool shiftCount(ExecState*, unsigned count);
6fe7ccc8 A	200	bool unshiftCount(ExecState*, unsigned count);
14957cd0	201
f9bf01c6	202	bool canGetIndex(unsigned i) { return i < m_vectorLength && m_storage->m_vector[i]; }
ba379fdc	203	JSValue getIndex(unsigned i)
9dae56ea A	204	{
9dae56ea A	205	ASSERT(canGetIndex(i));
14957cd0	206	return m_storage->m_vector[i].get();
9dae56ea A	207	}
9dae56ea A	208
f9bf01c6	209	bool canSetIndex(unsigned i) { return i < m_vectorLength; }
14957cd0	210	void setIndex(JSGlobalData& globalData, unsigned i, JSValue v)
9dae56ea A	211	{
9dae56ea A	212	ASSERT(canSetIndex(i));
14957cd0 A	213
14957cd0 A	214	WriteBarrier<Unknown>& x = m_storage->m_vector[i];
f9bf01c6	215	if (!x) {
14957cd0 A	216	ArrayStorage *storage = m_storage;
	217	++storage->m_numValuesInVector;
	218	if (i >= storage->m_length)
	219	storage->m_length = i + 1;
f9bf01c6	220	}
14957cd0 A	221	x.set(globalData, this, v);
	222	}
	223
6fe7ccc8	224	inline void initializeIndex(JSGlobalData& globalData, unsigned i, JSValue v)
14957cd0 A	225	{
	226	ASSERT(canSetIndex(i));
	227	ArrayStorage *storage = m_storage;
	228	#if CHECK_ARRAY_CONSISTENCY
	229	ASSERT(storage->m_inCompactInitialization);
6fe7ccc8 A	230	// Check that we are initializing the next index in sequence.
	231	ASSERT(i == storage->m_initializationIndex);
	232	// tryCreateUninitialized set m_numValuesInVector to the initialLength,
	233	// check we do not try to initialize more than this number of properties.
	234	ASSERT(storage->m_initializationIndex < storage->m_numValuesInVector);
	235	storage->m_initializationIndex++;
14957cd0	236	#endif
6fe7ccc8 A	237	ASSERT(i < storage->m_length);
6fe7ccc8 A	238	ASSERT(i < storage->m_numValuesInVector);
14957cd0	239	storage->m_vector[i].set(globalData, this, v);
9dae56ea A	240	}
9dae56ea A	241
6fe7ccc8 A	242	inline void completeInitialization(unsigned newLength)
	243	{
	244	// Check that we have initialized as meny properties as we think we have.
	245	ASSERT_UNUSED(newLength, newLength == m_storage->m_length);
	246	#if CHECK_ARRAY_CONSISTENCY
	247	// Check that the number of propreties initialized matches the initialLength.
	248	ASSERT(m_storage->m_initializationIndex == m_storage->m_numValuesInVector);
	249	ASSERT(m_storage->m_inCompactInitialization);
	250	m_storage->m_inCompactInitialization = false;
	251	#endif
	252	}
	253
	254	bool inSparseMode()
	255	{
	256	SparseArrayValueMap* map = m_sparseValueMap;
	257	return map && map->sparseMode();
	258	}
	259
ba379fdc	260	void fillArgList(ExecState*, MarkedArgumentBuffer&);
6fe7ccc8	261	void copyToArguments(ExecState, CallFrame, uint32_t length);
9dae56ea	262
6fe7ccc8	263	static Structure* createStructure(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype)
9dae56ea	264	{
6fe7ccc8	265	return Structure::create(globalData, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), &s_info);
9dae56ea	266	}
f9bf01c6	267
14957cd0 A	268	static ptrdiff_t storageOffset()
	269	{
	270	return OBJECT_OFFSETOF(JSArray, m_storage);
	271	}
	272
	273	static ptrdiff_t vectorLengthOffset()
	274	{
	275	return OBJECT_OFFSETOF(JSArray, m_vectorLength);
	276	}
9dae56ea	277
6fe7ccc8 A	278	JS_EXPORT_PRIVATE static void visitChildren(JSCell*, SlotVisitor&);
	279
	280	void enterDictionaryMode(JSGlobalData&);
	281
9dae56ea	282	protected:
14957cd0	283	static const unsigned StructureFlags = OverridesGetOwnPropertySlot \| OverridesVisitChildren \| OverridesGetPropertyNames \| JSObject::StructureFlags;
6fe7ccc8	284	static void put(JSCell, ExecState, const Identifier& propertyName, JSValue, PutPropertySlot&);
9dae56ea	285
6fe7ccc8 A	286	static bool deleteProperty(JSCell, ExecState, const Identifier& propertyName);
	287	static bool deletePropertyByIndex(JSCell, ExecState, unsigned propertyName);
	288	static void getOwnPropertyNames(JSObject, ExecState, PropertyNameArray&, EnumerationMode);
	289
	290	JS_EXPORT_PRIVATE void* subclassData() const;
	291	JS_EXPORT_PRIVATE void setSubclassData(void*);
9dae56ea A	292
9dae56ea A	293	private:
6fe7ccc8 A	294	static size_t storageSize(unsigned vectorLength);
	295	bool isLengthWritable()
	296	{
	297	SparseArrayValueMap* map = m_sparseValueMap;
	298	return !map \|\| !map->lengthIsReadOnly();
	299	}
	300
	301	void setLengthWritable(ExecState*, bool writable);
	302	void putDescriptor(ExecState, SparseArrayEntry, PropertyDescriptor&, PropertyDescriptor& old);
	303	bool defineOwnNumericProperty(ExecState*, unsigned, PropertyDescriptor&, bool throwException);
	304	void allocateSparseMap(JSGlobalData&);
	305	void deallocateSparseMap();
	306
9dae56ea	307	bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&);
6fe7ccc8 A	308	void putByIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
6fe7ccc8 A	309	JS_EXPORT_PRIVATE bool putDirectIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
9dae56ea	310
14957cd0	311	unsigned getNewVectorLength(unsigned desiredLength);
6fe7ccc8 A	312	bool increaseVectorLength(JSGlobalData&, unsigned newLength);
6fe7ccc8 A	313	bool unshiftCountSlowCase(JSGlobalData&, unsigned count);
9dae56ea	314
6fe7ccc8	315	unsigned compactForSorting(JSGlobalData&);
9dae56ea A	316
	317	enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck };
	318	void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck);
	319
14957cd0	320	unsigned m_vectorLength; // The valid length of m_vector
6fe7ccc8	321	unsigned m_indexBias; // The number of JSValue sized blocks before ArrayStorage.
14957cd0	322	ArrayStorage *m_storage;
6fe7ccc8 A	323
	324	// FIXME: Maybe SparseArrayValueMap should be put into its own JSCell?
	325	SparseArrayValueMap* m_sparseValueMap;
	326
	327	static ptrdiff_t sparseValueMapOffset() { return OBJECT_OFFSETOF(JSArray, m_sparseValueMap); }
	328	static ptrdiff_t indexBiasOffset() { return OBJECT_OFFSETOF(JSArray, m_indexBias); }
9dae56ea A	329	};
9dae56ea A	330
6fe7ccc8 A	331	inline JSArray* JSArray::create(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
	332	{
	333	JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
	334	array->finishCreation(globalData, initialLength);
	335	return array;
	336	}
	337
	338	inline JSArray* JSArray::tryCreateUninitialized(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
	339	{
	340	JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
	341	return array->tryFinishCreationUninitialized(globalData, initialLength);
	342	}
	343
ba379fdc	344	JSArray* asArray(JSValue);
9dae56ea	345
f9bf01c6 A	346	inline JSArray* asArray(JSCell* cell)
f9bf01c6 A	347	{
14957cd0	348	ASSERT(cell->inherits(&JSArray::s_info));
6fe7ccc8	349	return jsCast<JSArray*>(cell);
f9bf01c6	350	}
9dae56ea	351
ba379fdc	352	inline JSArray* asArray(JSValue value)
9dae56ea	353	{
f9bf01c6 A	354	return asArray(value.asCell());
	355	}
	356
6fe7ccc8 A	357	inline bool isJSArray(JSCell* cell) { return cell->classInfo() == &JSArray::s_info; }
6fe7ccc8 A	358	inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); }
9dae56ea	359
14957cd0 A	360	// Rule from ECMA 15.2 about what an array index is.
	361	// Must exactly match string form of an unsigned integer, and be less than 2^32 - 1.
	362	inline unsigned Identifier::toArrayIndex(bool& ok) const
f9bf01c6	363	{
14957cd0 A	364	unsigned i = toUInt32(ok);
	365	if (ok && i >= 0xFFFFFFFFU)
	366	ok = false;
	367	return i;
f9bf01c6	368	}
ba379fdc	369
6fe7ccc8 A	370	// The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
	371	// function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
	372	// size calculation cannot overflow. (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) +
	373	// (vectorLength * sizeof(WriteBarrier<Unknown>)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
	374	#define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>))
	375
	376	// These values have to be macros to be used in max() and min() without introducing
	377	// a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
	378	#define MIN_SPARSE_ARRAY_INDEX 10000U
	379	#define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
	380	inline size_t JSArray::storageSize(unsigned vectorLength)
	381	{
	382	ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH);
	383
	384	// MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH)
	385	// - as asserted above - the following calculation cannot overflow.
	386	size_t size = (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) + (vectorLength * sizeof(WriteBarrier<Unknown>));
	387	// Assertion to detect integer overflow in previous calculation (should not be possible, provided that
	388	// MAX_STORAGE_VECTOR_LENGTH is correctly defined).
	389	ASSERT(((size - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))));
	390
	391	return size;
	392	}
	393
	394	} // namespace JSC
9dae56ea A	395
9dae56ea A	396	#endif // JSArray_h