Rollout r200426 since it causes PLT regressions.
[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, 2012, 2015 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 "ArrayConventions.h"
25 #include "ButterflyInlines.h"
26 #include "JSObject.h"
27
28 namespace JSC {
29
30 class JSArray;
31 class LLIntOffsetsExtractor;
32
33 class JSArray : public JSNonFinalObject {
34     friend class LLIntOffsetsExtractor;
35     friend class Walker;
36     friend class JIT;
37
38 public:
39     typedef JSNonFinalObject Base;
40     static const unsigned StructureFlags = Base::StructureFlags | OverridesGetOwnPropertySlot | OverridesGetPropertyNames;
41
42     static size_t allocationSize(size_t inlineCapacity)
43     {
44         ASSERT_UNUSED(inlineCapacity, !inlineCapacity);
45         return sizeof(JSArray);
46     }
47         
48 protected:
49     explicit JSArray(VM& vm, Structure* structure, Butterfly* butterfly)
50         : JSNonFinalObject(vm, structure, butterfly)
51     {
52     }
53
54 public:
55     static JSArray* create(VM&, Structure*, unsigned initialLength = 0);
56     static JSArray* createWithButterfly(VM&, Structure*, Butterfly*);
57
58     // tryCreateUninitialized is used for fast construction of arrays whose size and
59     // contents are known at time of creation. Clients of this interface must:
60     //   - null-check the result (indicating out of memory, or otherwise unable to allocate vector).
61     //   - call 'initializeIndex' for all properties in sequence, for 0 <= i < initialLength.
62     static JSArray* tryCreateUninitialized(VM&, Structure*, unsigned initialLength);
63
64     JS_EXPORT_PRIVATE static bool defineOwnProperty(JSObject*, ExecState*, PropertyName, const PropertyDescriptor&, bool throwException);
65
66     JS_EXPORT_PRIVATE static bool getOwnPropertySlot(JSObject*, ExecState*, PropertyName, PropertySlot&);
67
68     DECLARE_EXPORT_INFO;
69
70     // OK if we know this is a JSArray, but not if it could be an object of a derived class; for RuntimeArray this always returns 0.
71     unsigned length() const { return getArrayLength(); }
72
73     // OK to use on new arrays, but not if it might be a RegExpMatchArray or RuntimeArray.
74     JS_EXPORT_PRIVATE bool setLength(ExecState*, unsigned, bool throwException = false);
75
76     JS_EXPORT_PRIVATE void push(ExecState*, JSValue);
77     JS_EXPORT_PRIVATE JSValue pop(ExecState*);
78
79     JSArray* fastSlice(ExecState&, unsigned startIndex, unsigned count);
80
81     static IndexingType fastConcatType(VM& vm, JSArray& firstArray, JSArray& secondArray)
82     {
83         IndexingType type = firstArray.indexingType();
84         if (type != secondArray.indexingType())
85             return NonArray;
86         if (type != ArrayWithDouble && type != ArrayWithInt32 && type != ArrayWithContiguous)
87             return NonArray;
88         if (firstArray.structure(vm)->holesMustForwardToPrototype(vm)
89             || secondArray.structure(vm)->holesMustForwardToPrototype(vm))
90             return NonArray;
91         return type;
92     }
93     EncodedJSValue fastConcatWith(ExecState&, JSArray&);
94
95     enum ShiftCountMode {
96         // This form of shift hints that we're doing queueing. With this assumption in hand,
97         // we convert to ArrayStorage, which has queue optimizations.
98         ShiftCountForShift,
99             
100         // This form of shift hints that we're just doing care and feeding on an array that
101         // is probably typically used for ordinary accesses. With this assumption in hand,
102         // we try to preserve whatever indexing type it has already.
103         ShiftCountForSplice
104     };
105
106     bool shiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
107     {
108         return shiftCountWithArrayStorage(exec->vm(), startIndex, count, ensureArrayStorage(exec->vm()));
109     }
110     bool shiftCountForSplice(ExecState* exec, unsigned& startIndex, unsigned count)
111     {
112         return shiftCountWithAnyIndexingType(exec, startIndex, count);
113     }
114     template<ShiftCountMode shiftCountMode>
115     bool shiftCount(ExecState* exec, unsigned& startIndex, unsigned count)
116     {
117         switch (shiftCountMode) {
118         case ShiftCountForShift:
119             return shiftCountForShift(exec, startIndex, count);
120         case ShiftCountForSplice:
121             return shiftCountForSplice(exec, startIndex, count);
122         default:
123             CRASH();
124             return false;
125         }
126     }
127         
128     bool unshiftCountForShift(ExecState* exec, unsigned startIndex, unsigned count)
129     {
130         return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
131     }
132     bool unshiftCountForSplice(ExecState* exec, unsigned startIndex, unsigned count)
133     {
134         return unshiftCountWithAnyIndexingType(exec, startIndex, count);
135     }
136     template<ShiftCountMode shiftCountMode>
137     bool unshiftCount(ExecState* exec, unsigned startIndex, unsigned count)
138     {
139         switch (shiftCountMode) {
140         case ShiftCountForShift:
141             return unshiftCountForShift(exec, startIndex, count);
142         case ShiftCountForSplice:
143             return unshiftCountForSplice(exec, startIndex, count);
144         default:
145             CRASH();
146             return false;
147         }
148     }
149
150     JS_EXPORT_PRIVATE void fillArgList(ExecState*, MarkedArgumentBuffer&);
151     JS_EXPORT_PRIVATE void copyToArguments(ExecState*, VirtualRegister firstElementDest, unsigned offset, unsigned length);
152
153     static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype, IndexingType indexingType)
154     {
155         return Structure::create(vm, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), info(), indexingType);
156     }
157         
158 protected:
159     static bool put(JSCell*, ExecState*, PropertyName, JSValue, PutPropertySlot&);
160
161     static bool deleteProperty(JSCell*, ExecState*, PropertyName);
162     JS_EXPORT_PRIVATE static void getOwnNonIndexPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
163
164 private:
165     bool isLengthWritable()
166     {
167         ArrayStorage* storage = arrayStorageOrNull();
168         if (!storage)
169             return true;
170         SparseArrayValueMap* map = storage->m_sparseMap.get();
171         return !map || !map->lengthIsReadOnly();
172     }
173         
174     bool shiftCountWithAnyIndexingType(ExecState*, unsigned& startIndex, unsigned count);
175     JS_EXPORT_PRIVATE bool shiftCountWithArrayStorage(VM&, unsigned startIndex, unsigned count, ArrayStorage*);
176
177     bool unshiftCountWithAnyIndexingType(ExecState*, unsigned startIndex, unsigned count);
178     bool unshiftCountWithArrayStorage(ExecState*, unsigned startIndex, unsigned count, ArrayStorage*);
179     bool unshiftCountSlowCase(VM&, bool, unsigned);
180
181     bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*);
182     void setLengthWritable(ExecState*, bool writable);
183 };
184
185 inline Butterfly* createContiguousArrayButterfly(VM& vm, JSCell* intendedOwner, unsigned length, unsigned& vectorLength)
186 {
187     IndexingHeader header;
188     vectorLength = std::max(length, BASE_VECTOR_LEN);
189     header.setVectorLength(vectorLength);
190     header.setPublicLength(length);
191     Butterfly* result = Butterfly::create(
192         vm, intendedOwner, 0, 0, true, header, vectorLength * sizeof(EncodedJSValue));
193     return result;
194 }
195
196 inline Butterfly* createArrayButterfly(VM& vm, JSCell* intendedOwner, unsigned initialLength)
197 {
198     Butterfly* butterfly = Butterfly::create(
199         vm, intendedOwner, 0, 0, true, baseIndexingHeaderForArray(initialLength),
200         ArrayStorage::sizeFor(BASE_VECTOR_LEN));
201     ArrayStorage* storage = butterfly->arrayStorage();
202     storage->m_indexBias = 0;
203     storage->m_sparseMap.clear();
204     storage->m_numValuesInVector = 0;
205     return butterfly;
206 }
207
208 Butterfly* createArrayButterflyInDictionaryIndexingMode(
209     VM&, JSCell* intendedOwner, unsigned initialLength);
210
211 inline JSArray* JSArray::create(VM& vm, Structure* structure, unsigned initialLength)
212 {
213     Butterfly* butterfly;
214     if (LIKELY(!hasAnyArrayStorage(structure->indexingType()))) {
215         ASSERT(
216             hasUndecided(structure->indexingType())
217             || hasInt32(structure->indexingType())
218             || hasDouble(structure->indexingType())
219             || hasContiguous(structure->indexingType()));
220         unsigned vectorLength;
221         butterfly = createContiguousArrayButterfly(vm, 0, initialLength, vectorLength);
222         ASSERT(initialLength < MIN_ARRAY_STORAGE_CONSTRUCTION_LENGTH);
223         if (hasDouble(structure->indexingType())) {
224             for (unsigned i = 0; i < vectorLength; ++i)
225                 butterfly->contiguousDouble()[i] = PNaN;
226         }
227     } else {
228         ASSERT(
229             structure->indexingType() == ArrayWithSlowPutArrayStorage
230             || structure->indexingType() == ArrayWithArrayStorage);
231         butterfly = createArrayButterfly(vm, 0, initialLength);
232     }
233
234     return createWithButterfly(vm, structure, butterfly);
235 }
236
237 inline JSArray* JSArray::tryCreateUninitialized(VM& vm, Structure* structure, unsigned initialLength)
238 {
239     unsigned vectorLength = std::max(BASE_VECTOR_LEN, initialLength);
240     if (vectorLength > MAX_STORAGE_VECTOR_LENGTH)
241         return 0;
242
243     unsigned outOfLineStorage = structure->outOfLineCapacity();
244
245     Butterfly* butterfly;
246     if (LIKELY(!hasAnyArrayStorage(structure->indexingType()))) {
247         ASSERT(
248             hasUndecided(structure->indexingType())
249             || hasInt32(structure->indexingType())
250             || hasDouble(structure->indexingType())
251             || hasContiguous(structure->indexingType()));
252
253         void* temp;
254         if (!vm.heap.tryAllocateStorage(0, Butterfly::totalSize(0, outOfLineStorage, true, vectorLength * sizeof(EncodedJSValue)), &temp))
255             return 0;
256         butterfly = Butterfly::fromBase(temp, 0, outOfLineStorage);
257         butterfly->setVectorLength(vectorLength);
258         butterfly->setPublicLength(initialLength);
259         if (hasDouble(structure->indexingType())) {
260             for (unsigned i = initialLength; i < vectorLength; ++i)
261                 butterfly->contiguousDouble()[i] = PNaN;
262         }
263     } else {
264         void* temp;
265         if (!vm.heap.tryAllocateStorage(0, Butterfly::totalSize(0, outOfLineStorage, true, ArrayStorage::sizeFor(vectorLength)), &temp))
266             return 0;
267         butterfly = Butterfly::fromBase(temp, 0, outOfLineStorage);
268         *butterfly->indexingHeader() = indexingHeaderForArray(initialLength, vectorLength);
269         ArrayStorage* storage = butterfly->arrayStorage();
270         storage->m_indexBias = 0;
271         storage->m_sparseMap.clear();
272         storage->m_numValuesInVector = initialLength;
273     }
274
275     return createWithButterfly(vm, structure, butterfly);
276 }
277
278 inline JSArray* JSArray::createWithButterfly(VM& vm, Structure* structure, Butterfly* butterfly)
279 {
280     JSArray* array = new (NotNull, allocateCell<JSArray>(vm.heap)) JSArray(vm, structure, butterfly);
281     array->finishCreation(vm);
282     return array;
283 }
284
285 JSArray* asArray(JSValue);
286
287 inline JSArray* asArray(JSCell* cell)
288 {
289     ASSERT(cell->inherits(JSArray::info()));
290     return jsCast<JSArray*>(cell);
291 }
292
293 inline JSArray* asArray(JSValue value)
294 {
295     return asArray(value.asCell());
296 }
297
298 inline bool isJSArray(JSCell* cell)
299 {
300     return cell->classInfo() == JSArray::info();
301 }
302
303 inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); }
304
305 inline JSArray* constructArray(ExecState* exec, Structure* arrayStructure, const ArgList& values)
306 {
307     VM& vm = exec->vm();
308     unsigned length = values.size();
309     JSArray* array = JSArray::tryCreateUninitialized(vm, arrayStructure, length);
310
311     // FIXME: we should probably throw an out of memory error here, but
312     // when making this change we should check that all clients of this
313     // function will correctly handle an exception being thrown from here.
314     RELEASE_ASSERT(array);
315
316     for (unsigned i = 0; i < length; ++i)
317         array->initializeIndex(vm, i, values.at(i));
318     return array;
319 }
320     
321 inline JSArray* constructArray(ExecState* exec, Structure* arrayStructure, const JSValue* values, unsigned length)
322 {
323     VM& vm = exec->vm();
324     JSArray* array = JSArray::tryCreateUninitialized(vm, arrayStructure, length);
325
326     // FIXME: we should probably throw an out of memory error here, but
327     // when making this change we should check that all clients of this
328     // function will correctly handle an exception being thrown from here.
329     RELEASE_ASSERT(array);
330
331     for (unsigned i = 0; i < length; ++i)
332         array->initializeIndex(vm, i, values[i]);
333     return array;
334 }
335
336 inline JSArray* constructArrayNegativeIndexed(ExecState* exec, Structure* arrayStructure, const JSValue* values, unsigned length)
337 {
338     VM& vm = exec->vm();
339     JSArray* array = JSArray::tryCreateUninitialized(vm, arrayStructure, length);
340
341     // FIXME: we should probably throw an out of memory error here, but
342     // when making this change we should check that all clients of this
343     // function will correctly handle an exception being thrown from here.
344     RELEASE_ASSERT(array);
345
346     for (int i = 0; i < static_cast<int>(length); ++i)
347         array->initializeIndex(vm, i, values[-i]);
348     return array;
349 }
350
351 ALWAYS_INLINE unsigned getLength(ExecState* exec, JSObject* obj)
352 {
353     if (isJSArray(obj))
354         return jsCast<JSArray*>(obj)->length();
355     return obj->get(exec, exec->propertyNames().length).toUInt32(exec);
356 }
357
358 } // namespace JSC
359
360 #endif // JSArray_h