runtime/JSArray.h

   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
  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
  41 protected:
  42     explicit JSArray(VM& vm, Structure* structure, Butterfly* butterfly)
  43         : JSNonFinalObject(vm, structure, butterfly)
  44     {
  45     }
  46
  47 public:
  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
 137 protected:
 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
 144 private:
 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
 177 inline 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
 188 inline 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
 199 Butterfly* createArrayButterflyInDictionaryIndexingMode(VM&, unsigned initialLength);
 200
 201 inline 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
 228 inline 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
 269 JSArray* asArray(JSValue);
 270
 271 inline JSArray* asArray(JSCell* cell)
 272 {
 273     ASSERT(cell->inherits(&JSArray::s_info));
 274     return jsCast<JSArray*>(cell);
 275 }
 276
 277 inline JSArray* asArray(JSValue value)
 278 {
 279     return asArray(value.asCell());
 280 }
 281
 282 inline bool isJSArray(JSCell* cell) { return cell->classInfo() == &JSArray::s_info; }
 283 inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); }
 284
 285 inline 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
 301 inline 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