Implement fast path for op_new_array in the baseline JIT
[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
59         SparseArrayValueMap()
60             : m_flags(Normal)
61             , m_reportedCapacity(0)
62         {
63         }
64
65         void visitChildren(SlotVisitor&);
66
67         bool sparseMode()
68         {
69             return m_flags & SparseMode;
70         }
71
72         void setSparseMode()
73         {
74             m_flags = static_cast<Flags>(m_flags | SparseMode);
75         }
76
77         bool lengthIsReadOnly()
78         {
79             return m_flags & LengthIsReadOnly;
80         }
81
82         void setLengthIsReadOnly()
83         {
84             m_flags = static_cast<Flags>(m_flags | LengthIsReadOnly);
85         }
86
87         // These methods may mutate the contents of the map
88         void put(ExecState*, JSArray*, unsigned, JSValue);
89         std::pair<iterator, bool> add(JSArray*, unsigned);
90         iterator find(unsigned i) { return m_map.find(i); }
91         // This should ASSERT the remove is valid (check the result of the find).
92         void remove(iterator it) { m_map.remove(it); }
93         void remove(unsigned i) { m_map.remove(i); }
94
95         // These methods do not mutate the contents of the map.
96         iterator notFound() { return m_map.end(); }
97         bool isEmpty() const { return m_map.isEmpty(); }
98         bool contains(unsigned i) const { return m_map.contains(i); }
99         size_t size() const { return m_map.size(); }
100         // Only allow const begin/end iteration.
101         const_iterator begin() const { return m_map.begin(); }
102         const_iterator end() const { return m_map.end(); }
103
104     private:
105         Map m_map;
106         Flags m_flags;
107         size_t m_reportedCapacity;
108     };
109
110     // This struct holds the actual data values of an array.  A JSArray object points to it's contained ArrayStorage
111     // struct by pointing to m_vector.  To access the contained ArrayStorage struct, use the getStorage() and 
112     // setStorage() methods.  It is important to note that there may be space before the ArrayStorage that 
113     // is used to quick unshift / shift operation.  The actual allocated pointer is available by using:
114     //     getStorage() - m_indexBias * sizeof(JSValue)
115     struct ArrayStorage {
116         unsigned m_length; // The "length" property on the array
117         unsigned m_numValuesInVector;
118         void* m_allocBase; // Pointer to base address returned by malloc().  Keeping this pointer does eliminate false positives from the leak detector.
119 #if CHECK_ARRAY_CONSISTENCY
120         uintptr_t m_inCompactInitialization; // Needs to be a uintptr_t for alignment purposes.
121 #else
122         uintptr_t m_padding;
123 #endif
124         WriteBarrier<Unknown> m_vector[1];
125
126         static ptrdiff_t lengthOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_length); }
127         static ptrdiff_t numValuesInVectorOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_numValuesInVector); }
128         static ptrdiff_t allocBaseOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_allocBase); }
129         static ptrdiff_t vectorOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_vector); }
130     };
131
132     class JSArray : public JSNonFinalObject {
133         friend class LLIntOffsetsExtractor;
134         friend class Walker;
135         friend class JIT;
136
137     protected:
138         JS_EXPORT_PRIVATE explicit JSArray(JSGlobalData&, Structure*);
139
140         JS_EXPORT_PRIVATE void finishCreation(JSGlobalData&, unsigned initialLength = 0);
141         JS_EXPORT_PRIVATE JSArray* tryFinishCreationUninitialized(JSGlobalData&, unsigned initialLength);
142     
143     public:
144         typedef JSNonFinalObject Base;
145
146         static void finalize(JSCell*);
147
148         static JSArray* create(JSGlobalData&, Structure*, unsigned initialLength = 0);
149
150         // tryCreateUninitialized is used for fast construction of arrays whose size and
151         // contents are known at time of creation. Clients of this interface must:
152         //   - null-check the result (indicating out of memory, or otherwise unable to allocate vector).
153         //   - call 'initializeIndex' for all properties in sequence, for 0 <= i < initialLength.
154         //   - called 'completeInitialization' after all properties have been initialized.
155         static JSArray* tryCreateUninitialized(JSGlobalData&, Structure*, unsigned initialLength);
156
157         JS_EXPORT_PRIVATE static bool defineOwnProperty(JSObject*, ExecState*, const Identifier&, PropertyDescriptor&, bool throwException);
158
159         static bool getOwnPropertySlot(JSCell*, ExecState*, const Identifier&, PropertySlot&);
160         JS_EXPORT_PRIVATE static bool getOwnPropertySlotByIndex(JSCell*, ExecState*, unsigned propertyName, PropertySlot&);
161         static bool getOwnPropertyDescriptor(JSObject*, ExecState*, const Identifier&, PropertyDescriptor&);
162         static void putByIndex(JSCell*, ExecState*, unsigned propertyName, JSValue);
163
164         static JS_EXPORTDATA const ClassInfo s_info;
165         
166         unsigned length() const { return m_storage->m_length; }
167         // OK to use on new arrays, but not if it might be a RegExpMatchArray.
168         bool setLength(ExecState*, unsigned, bool throwException = false);
169
170         void sort(ExecState*);
171         void sort(ExecState*, JSValue compareFunction, CallType, const CallData&);
172         void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&);
173
174         void push(ExecState*, JSValue);
175         JSValue pop(ExecState*);
176
177         void shiftCount(ExecState*, unsigned count);
178         void unshiftCount(ExecState*, unsigned count);
179
180         bool canGetIndex(unsigned i) { return i < m_vectorLength && m_storage->m_vector[i]; }
181         JSValue getIndex(unsigned i)
182         {
183             ASSERT(canGetIndex(i));
184             return m_storage->m_vector[i].get();
185         }
186
187         bool canSetIndex(unsigned i) { return i < m_vectorLength; }
188         void setIndex(JSGlobalData& globalData, unsigned i, JSValue v)
189         {
190             ASSERT(canSetIndex(i));
191             
192             WriteBarrier<Unknown>& x = m_storage->m_vector[i];
193             if (!x) {
194                 ArrayStorage *storage = m_storage;
195                 ++storage->m_numValuesInVector;
196                 if (i >= storage->m_length)
197                     storage->m_length = i + 1;
198             }
199             x.set(globalData, this, v);
200         }
201         
202         inline void initializeIndex(JSGlobalData& globalData, unsigned i, JSValue v)
203         {
204             ASSERT(canSetIndex(i));
205             ArrayStorage *storage = m_storage;
206 #if CHECK_ARRAY_CONSISTENCY
207             ASSERT(storage->m_inCompactInitialization);
208 #endif
209             // Check that we are initializing the next index in sequence.
210             ASSERT_UNUSED(i, i == storage->m_length);
211             // tryCreateUninitialized set m_numValuesInVector to the initialLength,
212             // check we do not try to initialize more than this number of properties.
213             ASSERT(storage->m_length < storage->m_numValuesInVector);
214             // It is improtant that we increment length here, so that all newly added
215             // values in the array still get marked during the initialization phase.
216             storage->m_vector[storage->m_length++].set(globalData, this, v);
217         }
218
219         inline void completeInitialization(unsigned newLength)
220         {
221             // Check that we have initialized as meny properties as we think we have.
222             ASSERT_UNUSED(newLength, newLength == m_storage->m_length);
223             // Check that the number of propreties initialized matches the initialLength.
224             ASSERT(m_storage->m_length == m_storage->m_numValuesInVector);
225 #if CHECK_ARRAY_CONSISTENCY
226             ASSERT(m_storage->m_inCompactInitialization);
227             m_storage->m_inCompactInitialization = false;
228 #endif
229         }
230
231         bool inSparseMode()
232         {
233             SparseArrayValueMap* map = m_sparseValueMap;
234             return map && map->sparseMode();
235         }
236
237         void fillArgList(ExecState*, MarkedArgumentBuffer&);
238         void copyToArguments(ExecState*, CallFrame*, uint32_t length);
239
240         static Structure* createStructure(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype)
241         {
242             return Structure::create(globalData, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), &s_info);
243         }
244         
245         static ptrdiff_t storageOffset()
246         {
247             return OBJECT_OFFSETOF(JSArray, m_storage);
248         }
249
250         static ptrdiff_t vectorLengthOffset()
251         {
252             return OBJECT_OFFSETOF(JSArray, m_vectorLength);
253         }
254
255         JS_EXPORT_PRIVATE static void visitChildren(JSCell*, SlotVisitor&);
256
257         void enterDictionaryMode(JSGlobalData&);
258
259     protected:
260         static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesVisitChildren | OverridesGetPropertyNames | JSObject::StructureFlags;
261         static void put(JSCell*, ExecState*, const Identifier& propertyName, JSValue, PutPropertySlot&);
262
263         static bool deleteProperty(JSCell*, ExecState*, const Identifier& propertyName);
264         static bool deletePropertyByIndex(JSCell*, ExecState*, unsigned propertyName);
265         static void getOwnPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
266
267         JS_EXPORT_PRIVATE void* subclassData() const;
268         JS_EXPORT_PRIVATE void setSubclassData(void*);
269
270     private:
271         static size_t storageSize(unsigned vectorLength);
272         bool isLengthWritable()
273         {
274             SparseArrayValueMap* map = m_sparseValueMap;
275             return !map || !map->lengthIsReadOnly();
276         }
277
278         void setLengthWritable(ExecState*, bool writable);
279         void putDescriptor(ExecState*, SparseArrayEntry*, PropertyDescriptor&, PropertyDescriptor& old);
280         bool defineOwnNumericProperty(ExecState*, unsigned, PropertyDescriptor&, bool throwException);
281         void allocateSparseMap(JSGlobalData&);
282         void deallocateSparseMap();
283
284         bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&);
285         void putByIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue);
286
287         unsigned getNewVectorLength(unsigned desiredLength);
288         bool increaseVectorLength(JSGlobalData&, unsigned newLength);
289         bool unshiftCountSlowCase(JSGlobalData&, unsigned count);
290         
291         unsigned compactForSorting(JSGlobalData&);
292
293         enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck };
294         void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck);
295
296         unsigned m_vectorLength; // The valid length of m_vector
297         unsigned m_indexBias; // The number of JSValue sized blocks before ArrayStorage.
298         ArrayStorage *m_storage;
299
300         // FIXME: Maybe SparseArrayValueMap should be put into its own JSCell?
301         SparseArrayValueMap* m_sparseValueMap;
302         void* m_subclassData; // A JSArray subclass can use this to fill the vector lazily.
303
304         static ptrdiff_t sparseValueMapOffset() { return OBJECT_OFFSETOF(JSArray, m_sparseValueMap); }
305         static ptrdiff_t subclassDataOffset() { return OBJECT_OFFSETOF(JSArray, m_subclassData); }
306         static ptrdiff_t indexBiasOffset() { return OBJECT_OFFSETOF(JSArray, m_indexBias); }
307     };
308
309     inline JSArray* JSArray::create(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
310     {
311         JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
312         array->finishCreation(globalData, initialLength);
313         return array;
314     }
315
316     inline JSArray* JSArray::tryCreateUninitialized(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
317     {
318         JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
319         return array->tryFinishCreationUninitialized(globalData, initialLength);
320     }
321
322     JSArray* asArray(JSValue);
323
324     inline JSArray* asArray(JSCell* cell)
325     {
326         ASSERT(cell->inherits(&JSArray::s_info));
327         return static_cast<JSArray*>(cell);
328     }
329
330     inline JSArray* asArray(JSValue value)
331     {
332         return asArray(value.asCell());
333     }
334
335     inline bool isJSArray(JSCell* cell) { return cell->classInfo() == &JSArray::s_info; }
336     inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); }
337
338     // Rule from ECMA 15.2 about what an array index is.
339     // Must exactly match string form of an unsigned integer, and be less than 2^32 - 1.
340     inline unsigned Identifier::toArrayIndex(bool& ok) const
341     {
342         unsigned i = toUInt32(ok);
343         if (ok && i >= 0xFFFFFFFFU)
344             ok = false;
345         return i;
346     }
347
348 // The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
349 // function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
350 // size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) +
351 // (vectorLength * sizeof(WriteBarrier<Unknown>)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
352 #define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>))
353
354 // These values have to be macros to be used in max() and min() without introducing
355 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
356 #define MIN_SPARSE_ARRAY_INDEX 10000U
357 #define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
358     inline size_t JSArray::storageSize(unsigned vectorLength)
359     {
360         ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH);
361     
362         // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH)
363         // - as asserted above - the following calculation cannot overflow.
364         size_t size = (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) + (vectorLength * sizeof(WriteBarrier<Unknown>));
365         // Assertion to detect integer overflow in previous calculation (should not be possible, provided that
366         // MAX_STORAGE_VECTOR_LENGTH is correctly defined).
367         ASSERT(((size - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))));
368     
369         return size;
370     }
371     
372     } // namespace JSC
373
374 #endif // JSArray_h