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