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