[ES5] Implement Object.keys
[WebKit-https.git] / 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 namespace JSC {
27
28     typedef HashMap<unsigned, JSValue> SparseArrayValueMap;
29
30     struct ArrayStorage {
31         unsigned m_length;
32         unsigned m_vectorLength;
33         unsigned m_numValuesInVector;
34         SparseArrayValueMap* m_sparseValueMap;
35         void* lazyCreationData; // A JSArray subclass can use this to fill the vector lazily.
36         JSValue m_vector[1];
37     };
38
39     class JSArray : public JSObject {
40         friend class JIT;
41         friend class Walker;
42
43     public:
44         explicit JSArray(PassRefPtr<Structure>);
45         JSArray(PassRefPtr<Structure>, unsigned initialLength);
46         JSArray(PassRefPtr<Structure>, const ArgList& initialValues);
47         virtual ~JSArray();
48
49         virtual bool getOwnPropertySlot(ExecState*, const Identifier& propertyName, PropertySlot&);
50         virtual bool getOwnPropertySlot(ExecState*, unsigned propertyName, PropertySlot&);
51         virtual bool getOwnPropertyDescriptor(ExecState*, const Identifier&, PropertyDescriptor&);
52         virtual void put(ExecState*, unsigned propertyName, JSValue); // FIXME: Make protected and add setItem.
53
54         static JS_EXPORTDATA const ClassInfo info;
55
56         unsigned length() const { return m_storage->m_length; }
57         void setLength(unsigned); // OK to use on new arrays, but not if it might be a RegExpMatchArray.
58
59         void sort(ExecState*);
60         void sort(ExecState*, JSValue compareFunction, CallType, const CallData&);
61         void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&);
62
63         void push(ExecState*, JSValue);
64         JSValue pop();
65
66         bool canGetIndex(unsigned i) { return i < m_fastAccessCutoff; }
67         JSValue getIndex(unsigned i)
68         {
69             ASSERT(canGetIndex(i));
70             return m_storage->m_vector[i];
71         }
72
73         bool canSetIndex(unsigned i) { return i < m_fastAccessCutoff; }
74         JSValue setIndex(unsigned i, JSValue v)
75         {
76             ASSERT(canSetIndex(i));
77             return m_storage->m_vector[i] = v;
78         }
79
80         void fillArgList(ExecState*, MarkedArgumentBuffer&);
81         void copyToRegisters(ExecState*, Register*, uint32_t);
82
83         static PassRefPtr<Structure> createStructure(JSValue prototype)
84         {
85             return Structure::create(prototype, TypeInfo(ObjectType));
86         }
87         
88         inline void markChildrenDirect(MarkStack& markStack);
89
90     protected:
91         virtual void put(ExecState*, const Identifier& propertyName, JSValue, PutPropertySlot&);
92         virtual bool deleteProperty(ExecState*, const Identifier& propertyName);
93         virtual bool deleteProperty(ExecState*, unsigned propertyName);
94         virtual void getOwnPropertyNames(ExecState*, PropertyNameArray&);
95         virtual void markChildren(MarkStack&);
96
97         void* lazyCreationData();
98         void setLazyCreationData(void*);
99
100     private:
101         virtual const ClassInfo* classInfo() const { return &info; }
102
103         bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&);
104         void putSlowCase(ExecState*, unsigned propertyName, JSValue);
105
106         bool increaseVectorLength(unsigned newLength);
107         
108         unsigned compactForSorting();
109
110         enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck };
111         void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck);
112
113         unsigned m_fastAccessCutoff;
114         ArrayStorage* m_storage;
115     };
116
117     JSArray* asArray(JSValue);
118
119     JSArray* constructEmptyArray(ExecState*);
120     JSArray* constructEmptyArray(ExecState*, unsigned initialLength);
121     JSArray* constructArray(ExecState*, JSValue singleItemValue);
122     JSArray* constructArray(ExecState*, const ArgList& values);
123
124     inline JSArray* asArray(JSCell* cell)
125     {
126         ASSERT(cell->inherits(&JSArray::info));
127         return static_cast<JSArray*>(cell);
128     }
129
130     inline JSArray* asArray(JSValue value)
131     {
132         return asArray(value.asCell());
133     }
134
135     inline bool isJSArray(JSGlobalData* globalData, JSValue v)
136     {
137         return v.isCell() && v.asCell()->vptr() == globalData->jsArrayVPtr;
138     }
139     inline bool isJSArray(JSGlobalData* globalData, JSCell* cell) { return cell->vptr() == globalData->jsArrayVPtr; }
140
141     inline void JSArray::markChildrenDirect(MarkStack& markStack)
142     {
143         JSObject::markChildrenDirect(markStack);
144         
145         ArrayStorage* storage = m_storage;
146
147         unsigned usedVectorLength = std::min(storage->m_length, storage->m_vectorLength);
148         markStack.appendValues(storage->m_vector, usedVectorLength, MayContainNullValues);
149
150         if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
151             SparseArrayValueMap::iterator end = map->end();
152             for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
153                 markStack.append(it->second);
154         }
155     }
156
157     inline void MarkStack::markChildren(JSCell* cell)
158     {
159         ASSERT(Heap::isCellMarked(cell));
160         if (cell->structure()->typeInfo().hasDefaultMark()) {
161 #ifdef NDEBUG
162             asObject(cell)->markChildrenDirect(*this);
163 #else
164             ASSERT(!m_isCheckingForDefaultMarkViolation);
165             m_isCheckingForDefaultMarkViolation = true;
166             cell->markChildren(*this);
167             ASSERT(m_isCheckingForDefaultMarkViolation);
168             m_isCheckingForDefaultMarkViolation = false;
169 #endif
170             return;
171         }
172         if (cell->vptr() == m_jsArrayVPtr) {
173             asArray(cell)->markChildrenDirect(*this);
174             return;
175         }
176         cell->markChildren(*this);
177     }
178
179     inline void MarkStack::drain()
180     {
181         while (!m_markSets.isEmpty() || !m_values.isEmpty()) {
182             while (!m_markSets.isEmpty() && m_values.size() < 50) {
183                 ASSERT(!m_markSets.isEmpty());
184                 MarkSet& current = m_markSets.last();
185                 ASSERT(current.m_values);
186                 JSValue* end = current.m_end;
187                 ASSERT(current.m_values);
188                 ASSERT(current.m_values != end);
189             findNextUnmarkedNullValue:
190                 ASSERT(current.m_values != end);
191                 JSValue value = *current.m_values;
192                 current.m_values++;
193
194                 JSCell* cell;
195                 if (!value || !value.isCell() || Heap::isCellMarked(cell = value.asCell())) {
196                     if (current.m_values == end) {
197                         m_markSets.removeLast();
198                         continue;
199                     }
200                     goto findNextUnmarkedNullValue;
201                 }
202
203                 Heap::markCell(cell);
204                 if (cell->structure()->typeInfo().type() < CompoundType) {
205                     if (current.m_values == end) {
206                         m_markSets.removeLast();
207                         continue;
208                     }
209                     goto findNextUnmarkedNullValue;
210                 }
211
212                 if (current.m_values == end)
213                     m_markSets.removeLast();
214
215                 markChildren(cell);
216             }
217             while (!m_values.isEmpty())
218                 markChildren(m_values.removeLast());
219         }
220     }
221     
222 } // namespace JSC
223
224 #endif // JSArray_h