Remove m_subclassData from JSArray, move the attribute to subclass as needed
[WebKit-https.git] / Source / JavaScriptCore / runtime / JSArray.h
1 /*
2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2003, 2007, 2008, 2009 Apple Inc. All rights reserved.
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
26 #define CHECK_ARRAY_CONSISTENCY 0
27
28 namespace JSC {
29
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     };
111
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)
117     struct ArrayStorage {
118         unsigned m_length; // The "length" property on the array
119         unsigned m_numValuesInVector;
120         void* m_allocBase; // Pointer to base address returned by malloc().  Keeping this pointer does eliminate false positives from the leak detector.
121 #if CHECK_ARRAY_CONSISTENCY
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;
127 #endif
128         WriteBarrier<Unknown> m_vector[1];
129
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     };
135
136     class JSArray : public JSNonFinalObject {
137         friend class LLIntOffsetsExtractor;
138         friend class Walker;
139         friend class JIT;
140
141     protected:
142         JS_EXPORT_PRIVATE explicit JSArray(JSGlobalData&, Structure*);
143
144         JS_EXPORT_PRIVATE void finishCreation(JSGlobalData&, unsigned initialLength = 0);
145         JS_EXPORT_PRIVATE JSArray* tryFinishCreationUninitialized(JSGlobalData&, unsigned initialLength);
146     
147     public:
148         typedef JSNonFinalObject Base;
149
150         static void finalize(JSCell*);
151
152         static JSArray* create(JSGlobalData&, Structure*, unsigned initialLength = 0);
153
154         // tryCreateUninitialized is used for fast construction of arrays whose size and
155         // contents are known at time of creation. Clients of this interface must:
156         //   - null-check the result (indicating out of memory, or otherwise unable to allocate vector).
157         //   - call 'initializeIndex' for all properties in sequence, for 0 <= i < initialLength.
158         //   - called 'completeInitialization' after all properties have been initialized.
159         static JSArray* tryCreateUninitialized(JSGlobalData&, Structure*, unsigned initialLength);
160
161         JS_EXPORT_PRIVATE static bool defineOwnProperty(JSObject*, ExecState*, const Identifier&, PropertyDescriptor&, bool throwException);
162
163         static bool getOwnPropertySlot(JSCell*, ExecState*, const Identifier&, PropertySlot&);
164         JS_EXPORT_PRIVATE static bool getOwnPropertySlotByIndex(JSCell*, ExecState*, unsigned propertyName, PropertySlot&);
165         static bool getOwnPropertyDescriptor(JSObject*, ExecState*, const Identifier&, PropertyDescriptor&);
166         static void putByIndex(JSCell*, ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
167         // This is similar to the JSObject::putDirect* methods:
168         //  - the prototype chain is not consulted
169         //  - accessors are not called.
170         // This method creates a property with attributes writable, enumerable and configurable all set to true.
171         bool putDirectIndex(ExecState* exec, unsigned propertyName, JSValue value, bool shouldThrow = true)
172         {
173             if (canSetIndex(propertyName)) {
174                 setIndex(exec->globalData(), propertyName, value);
175                 return true;
176             }
177             return putDirectIndexBeyondVectorLength(exec, propertyName, value, shouldThrow);
178         }
179
180         static JS_EXPORTDATA const ClassInfo s_info;
181         
182         unsigned length() const { return m_storage->m_length; }
183         // OK to use on new arrays, but not if it might be a RegExpMatchArray.
184         bool setLength(ExecState*, unsigned, bool throwException = false);
185
186         void sort(ExecState*);
187         void sort(ExecState*, JSValue compareFunction, CallType, const CallData&);
188         void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&);
189
190         void push(ExecState*, JSValue);
191         JSValue pop(ExecState*);
192
193         bool shiftCount(ExecState*, unsigned count);
194         bool unshiftCount(ExecState*, unsigned count);
195
196         bool canGetIndex(unsigned i) { return i < m_vectorLength && m_storage->m_vector[i]; }
197         JSValue getIndex(unsigned i)
198         {
199             ASSERT(canGetIndex(i));
200             return m_storage->m_vector[i].get();
201         }
202
203         bool canSetIndex(unsigned i) { return i < m_vectorLength; }
204         void setIndex(JSGlobalData& globalData, unsigned i, JSValue v)
205         {
206             ASSERT(canSetIndex(i));
207             
208             WriteBarrier<Unknown>& x = m_storage->m_vector[i];
209             if (!x) {
210                 ArrayStorage *storage = m_storage;
211                 ++storage->m_numValuesInVector;
212                 if (i >= storage->m_length)
213                     storage->m_length = i + 1;
214             }
215             x.set(globalData, this, v);
216         }
217         
218         inline void initializeIndex(JSGlobalData& globalData, unsigned i, JSValue v)
219         {
220             ASSERT(canSetIndex(i));
221             ArrayStorage *storage = m_storage;
222 #if CHECK_ARRAY_CONSISTENCY
223             ASSERT(storage->m_inCompactInitialization);
224             // Check that we are initializing the next index in sequence.
225             ASSERT(i == storage->m_initializationIndex);
226             // tryCreateUninitialized set m_numValuesInVector to the initialLength,
227             // check we do not try to initialize more than this number of properties.
228             ASSERT(storage->m_initializationIndex < storage->m_numValuesInVector);
229             storage->m_initializationIndex++;
230 #endif
231             ASSERT(i < storage->m_length);
232             ASSERT(i < storage->m_numValuesInVector);
233             storage->m_vector[i].set(globalData, this, v);
234         }
235
236         inline void completeInitialization(unsigned newLength)
237         {
238             // Check that we have initialized as meny properties as we think we have.
239             ASSERT_UNUSED(newLength, newLength == m_storage->m_length);
240 #if CHECK_ARRAY_CONSISTENCY
241             // Check that the number of propreties initialized matches the initialLength.
242             ASSERT(m_storage->m_initializationIndex == m_storage->m_numValuesInVector);
243             ASSERT(m_storage->m_inCompactInitialization);
244             m_storage->m_inCompactInitialization = false;
245 #endif
246         }
247
248         bool inSparseMode()
249         {
250             SparseArrayValueMap* map = m_sparseValueMap;
251             return map && map->sparseMode();
252         }
253
254         void fillArgList(ExecState*, MarkedArgumentBuffer&);
255         void copyToArguments(ExecState*, CallFrame*, uint32_t length);
256
257         static Structure* createStructure(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype)
258         {
259             return Structure::create(globalData, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), &s_info);
260         }
261         
262         static ptrdiff_t storageOffset()
263         {
264             return OBJECT_OFFSETOF(JSArray, m_storage);
265         }
266
267         static ptrdiff_t vectorLengthOffset()
268         {
269             return OBJECT_OFFSETOF(JSArray, m_vectorLength);
270         }
271
272         JS_EXPORT_PRIVATE static void visitChildren(JSCell*, SlotVisitor&);
273
274         void enterDictionaryMode(JSGlobalData&);
275
276     protected:
277         static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesVisitChildren | OverridesGetPropertyNames | JSObject::StructureFlags;
278         static void put(JSCell*, ExecState*, const Identifier& propertyName, JSValue, PutPropertySlot&);
279
280         static bool deleteProperty(JSCell*, ExecState*, const Identifier& propertyName);
281         static bool deletePropertyByIndex(JSCell*, ExecState*, unsigned propertyName);
282         static void getOwnPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
283
284         JS_EXPORT_PRIVATE void* subclassData() const;
285         JS_EXPORT_PRIVATE void setSubclassData(void*);
286
287     private:
288         static size_t storageSize(unsigned vectorLength);
289         bool isLengthWritable()
290         {
291             SparseArrayValueMap* map = m_sparseValueMap;
292             return !map || !map->lengthIsReadOnly();
293         }
294
295         void setLengthWritable(ExecState*, bool writable);
296         void putDescriptor(ExecState*, SparseArrayEntry*, PropertyDescriptor&, PropertyDescriptor& old);
297         bool defineOwnNumericProperty(ExecState*, unsigned, PropertyDescriptor&, bool throwException);
298         void allocateSparseMap(JSGlobalData&);
299         void deallocateSparseMap();
300
301         bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&);
302         void putByIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
303         JS_EXPORT_PRIVATE bool putDirectIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
304
305         unsigned getNewVectorLength(unsigned desiredLength);
306         bool increaseVectorLength(JSGlobalData&, unsigned newLength);
307         bool unshiftCountSlowCase(JSGlobalData&, unsigned count);
308         
309         unsigned compactForSorting(JSGlobalData&);
310
311         enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck };
312         void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck);
313
314         unsigned m_vectorLength; // The valid length of m_vector
315         unsigned m_indexBias; // The number of JSValue sized blocks before ArrayStorage.
316         ArrayStorage *m_storage;
317
318         // FIXME: Maybe SparseArrayValueMap should be put into its own JSCell?
319         SparseArrayValueMap* m_sparseValueMap;
320
321         static ptrdiff_t sparseValueMapOffset() { return OBJECT_OFFSETOF(JSArray, m_sparseValueMap); }
322         static ptrdiff_t indexBiasOffset() { return OBJECT_OFFSETOF(JSArray, m_indexBias); }
323     };
324
325     inline JSArray* JSArray::create(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
326     {
327         JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
328         array->finishCreation(globalData, initialLength);
329         return array;
330     }
331
332     inline JSArray* JSArray::tryCreateUninitialized(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
333     {
334         JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
335         return array->tryFinishCreationUninitialized(globalData, initialLength);
336     }
337
338     JSArray* asArray(JSValue);
339
340     inline JSArray* asArray(JSCell* cell)
341     {
342         ASSERT(cell->inherits(&JSArray::s_info));
343         return jsCast<JSArray*>(cell);
344     }
345
346     inline JSArray* asArray(JSValue value)
347     {
348         return asArray(value.asCell());
349     }
350
351     inline bool isJSArray(JSCell* cell) { return cell->classInfo() == &JSArray::s_info; }
352     inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); }
353
354     // Rule from ECMA 15.2 about what an array index is.
355     // Must exactly match string form of an unsigned integer, and be less than 2^32 - 1.
356     inline unsigned Identifier::toArrayIndex(bool& ok) const
357     {
358         unsigned i = toUInt32(ok);
359         if (ok && i >= 0xFFFFFFFFU)
360             ok = false;
361         return i;
362     }
363
364 // The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
365 // function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
366 // size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) +
367 // (vectorLength * sizeof(WriteBarrier<Unknown>)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
368 #define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>))
369
370 // These values have to be macros to be used in max() and min() without introducing
371 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
372 #define MIN_SPARSE_ARRAY_INDEX 10000U
373 #define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
374     inline size_t JSArray::storageSize(unsigned vectorLength)
375     {
376         ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH);
377     
378         // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH)
379         // - as asserted above - the following calculation cannot overflow.
380         size_t size = (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) + (vectorLength * sizeof(WriteBarrier<Unknown>));
381         // Assertion to detect integer overflow in previous calculation (should not be possible, provided that
382         // MAX_STORAGE_VECTOR_LENGTH is correctly defined).
383         ASSERT(((size - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))));
384     
385         return size;
386     }
387     
388     } // namespace JSC
389
390 #endif // JSArray_h