de28b65bb83df1e7471c692948bfcd357cfa4916
[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     typedef HashMap<unsigned, JSValue> SparseArrayValueMap;
31
32     // This struct holds the actual data values of an array.  A JSArray object points to it's contained ArrayStorage
33     // struct by pointing to m_vector.  To access the contained ArrayStorage struct, use the getStorage() and 
34     // setStorage() methods.  It is important to note that there may be space before the ArrayStorage that 
35     // is used to quick unshift / shift operation.  The actual allocated pointer is available by using:
36     //     getStorage() - m_indexBias * sizeof(JSValue)
37     struct ArrayStorage {
38         unsigned m_length; // The "length" property on the array
39         unsigned m_numValuesInVector;
40         SparseArrayValueMap* m_sparseValueMap;
41         void* subclassData; // A JSArray subclass can use this to fill the vector lazily.
42         void* m_allocBase; // Pointer to base address returned by malloc().  Keeping this pointer does eliminate false positives from the leak detector.
43         size_t reportedMapCapacity;
44 #if CHECK_ARRAY_CONSISTENCY
45         bool m_inCompactInitialization;
46 #endif
47         JSValue m_vector[1];
48     };
49
50     // The CreateCompact creation mode is used for fast construction of arrays
51     // whose size and contents are known at time of creation.
52     //
53     // There are two obligations when using this mode:
54     //
55     //   - uncheckedSetIndex() must be used when initializing the array.
56     //   - setLength() must be called after initialization.
57
58     enum ArrayCreationMode { CreateCompact, CreateInitialized };
59
60     class JSArray : public JSObject {
61         friend class JIT;
62         friend class Walker;
63
64     public:
65         enum VPtrStealingHackType { VPtrStealingHack };
66         JSArray(VPtrStealingHackType);
67
68         explicit JSArray(NonNullPassRefPtr<Structure>);
69         JSArray(NonNullPassRefPtr<Structure>, unsigned initialLength, ArrayCreationMode);
70         JSArray(NonNullPassRefPtr<Structure>, const ArgList& initialValues);
71         virtual ~JSArray();
72
73         virtual bool getOwnPropertySlot(ExecState*, const Identifier& propertyName, PropertySlot&);
74         virtual bool getOwnPropertySlot(ExecState*, unsigned propertyName, PropertySlot&);
75         virtual bool getOwnPropertyDescriptor(ExecState*, const Identifier&, PropertyDescriptor&);
76         virtual void put(ExecState*, unsigned propertyName, JSValue); // FIXME: Make protected and add setItem.
77
78         static JS_EXPORTDATA const ClassInfo info;
79         
80         unsigned length() const { return m_storage->m_length; }
81         void setLength(unsigned); // OK to use on new arrays, but not if it might be a RegExpMatchArray.
82
83         void sort(ExecState*);
84         void sort(ExecState*, JSValue compareFunction, CallType, const CallData&);
85         void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&);
86
87         void push(ExecState*, JSValue);
88         JSValue pop();
89
90         void shiftCount(ExecState*, int count);
91         void unshiftCount(ExecState*, int count);
92
93         bool canGetIndex(unsigned i) { return i < m_vectorLength && m_storage->m_vector[i]; }
94         JSValue getIndex(unsigned i)
95         {
96             ASSERT(canGetIndex(i));
97             return m_storage->m_vector[i];
98         }
99
100         bool canSetIndex(unsigned i) { return i < m_vectorLength; }
101         void setIndex(unsigned i, JSValue v)
102         {
103             ASSERT(canSetIndex(i));
104             
105             JSValue& x = m_storage->m_vector[i];
106             if (!x) {
107                 ArrayStorage *storage = m_storage;
108                 ++storage->m_numValuesInVector;
109                 if (i >= storage->m_length)
110                     storage->m_length = i + 1;
111             }
112             x = v;
113         }
114         
115         void uncheckedSetIndex(unsigned i, JSValue v)
116         {
117             ASSERT(canSetIndex(i));
118             ArrayStorage *storage = m_storage;
119 #if CHECK_ARRAY_CONSISTENCY
120             ASSERT(storage->m_inCompactInitialization);
121 #endif
122             storage->m_vector[i] = v;
123         }
124
125         void fillArgList(ExecState*, MarkedArgumentBuffer&);
126         void copyToRegisters(ExecState*, Register*, uint32_t);
127
128         static PassRefPtr<Structure> createStructure(JSValue prototype)
129         {
130             return Structure::create(prototype, TypeInfo(ObjectType, StructureFlags), AnonymousSlotCount);
131         }
132         
133         inline void markChildrenDirect(MarkStack& markStack);
134
135     protected:
136         static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesMarkChildren | OverridesGetPropertyNames | JSObject::StructureFlags;
137         virtual void put(ExecState*, const Identifier& propertyName, JSValue, PutPropertySlot&);
138         virtual bool deleteProperty(ExecState*, const Identifier& propertyName);
139         virtual bool deleteProperty(ExecState*, unsigned propertyName);
140         virtual void getOwnPropertyNames(ExecState*, PropertyNameArray&, EnumerationMode mode = ExcludeDontEnumProperties);
141         virtual void markChildren(MarkStack&);
142
143         void* subclassData() const;
144         void setSubclassData(void*);
145         
146     private:
147         virtual const ClassInfo* classInfo() const { return &info; }
148
149         bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&);
150         void putSlowCase(ExecState*, unsigned propertyName, JSValue);
151
152         unsigned getNewVectorLength(unsigned desiredLength);
153         bool increaseVectorLength(unsigned newLength);
154         bool increaseVectorPrefixLength(unsigned newLength);
155         
156         unsigned compactForSorting();
157
158         enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck };
159         void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck);
160
161         unsigned m_vectorLength; // The valid length of m_vector
162         int m_indexBias; // The number of JSValue sized blocks before ArrayStorage.
163         ArrayStorage *m_storage;
164     };
165
166     JSArray* asArray(JSValue);
167
168     inline JSArray* asArray(JSCell* cell)
169     {
170         ASSERT(cell->inherits(&JSArray::info));
171         return static_cast<JSArray*>(cell);
172     }
173
174     inline JSArray* asArray(JSValue value)
175     {
176         return asArray(value.asCell());
177     }
178
179     inline bool isJSArray(JSGlobalData* globalData, JSValue v)
180     {
181         return v.isCell() && v.asCell()->vptr() == globalData->jsArrayVPtr;
182     }
183     inline bool isJSArray(JSGlobalData* globalData, JSCell* cell) { return cell->vptr() == globalData->jsArrayVPtr; }
184
185     inline void JSArray::markChildrenDirect(MarkStack& markStack)
186     {
187         JSObject::markChildrenDirect(markStack);
188         
189         ArrayStorage* storage = m_storage;
190
191         unsigned usedVectorLength = std::min(storage->m_length, m_vectorLength);
192         markStack.appendValues(storage->m_vector, usedVectorLength, MayContainNullValues);
193
194         if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
195             SparseArrayValueMap::iterator end = map->end();
196             for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
197                 markStack.append(it->second);
198         }
199     }
200
201     inline void MarkStack::markChildren(JSCell* cell)
202     {
203         ASSERT(Heap::isCellMarked(cell));
204         if (!cell->structure()->typeInfo().overridesMarkChildren()) {
205 #ifdef NDEBUG
206             asObject(cell)->markChildrenDirect(*this);
207 #else
208             ASSERT(!m_isCheckingForDefaultMarkViolation);
209             m_isCheckingForDefaultMarkViolation = true;
210             cell->markChildren(*this);
211             ASSERT(m_isCheckingForDefaultMarkViolation);
212             m_isCheckingForDefaultMarkViolation = false;
213 #endif
214             return;
215         }
216         if (cell->vptr() == m_jsArrayVPtr) {
217             asArray(cell)->markChildrenDirect(*this);
218             return;
219         }
220         cell->markChildren(*this);
221     }
222
223     inline void MarkStack::drain()
224     {
225 #if !ASSERT_DISABLED
226         ASSERT(!m_isDraining);
227         m_isDraining = true;
228 #endif
229         while (!m_markSets.isEmpty() || !m_values.isEmpty()) {
230             while (!m_markSets.isEmpty() && m_values.size() < 50) {
231                 ASSERT(!m_markSets.isEmpty());
232                 MarkSet& current = m_markSets.last();
233                 ASSERT(current.m_values);
234                 JSValue* end = current.m_end;
235                 ASSERT(current.m_values);
236                 ASSERT(current.m_values != end);
237             findNextUnmarkedNullValue:
238                 ASSERT(current.m_values != end);
239                 JSValue value = *current.m_values;
240                 current.m_values++;
241
242                 JSCell* cell;
243                 if (!value || !value.isCell() || Heap::checkMarkCell(cell = value.asCell())) {
244                     if (current.m_values == end) {
245                         m_markSets.removeLast();
246                         continue;
247                     }
248                     goto findNextUnmarkedNullValue;
249                 }
250
251                 if (cell->structure()->typeInfo().type() < CompoundType) {
252                     if (current.m_values == end) {
253                         m_markSets.removeLast();
254                         continue;
255                     }
256                     goto findNextUnmarkedNullValue;
257                 }
258
259                 if (current.m_values == end)
260                     m_markSets.removeLast();
261
262                 markChildren(cell);
263             }
264             while (!m_values.isEmpty())
265                 markChildren(m_values.removeLast());
266         }
267 #if !ASSERT_DISABLED
268         m_isDraining = false;
269 #endif
270     }
271
272     // Rule from ECMA 15.2 about what an array index is.
273     // Must exactly match string form of an unsigned integer, and be less than 2^32 - 1.
274     inline unsigned Identifier::toArrayIndex(bool& ok) const
275     {
276         unsigned i = toUInt32(ok);
277         if (ok && i >= 0xFFFFFFFFU)
278             ok = false;
279         return i;
280     }
281
282 } // namespace JSC
283
284 #endif // JSArray_h