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 #define CHECK_ARRAY_CONSISTENCY 0
  27
  28 namespace JSC {
  29
  30     class JSArray;
  31     class LLIntOffsetsExtractor;
  32
  33     struct SparseArrayEntry : public WriteBarrier<Unknown> {
  34         typedef WriteBarrier<Unknown> Base;
  35
  36         SparseArrayEntry() : attributes(0) {}
  37
  38         JSValue get(ExecState*, JSArray*) const;
  39         void get(PropertySlot&) const;
  40         void get(PropertyDescriptor&) const;
  41         JSValue getNonSparseMode() const;
  42
  43         unsigned attributes;
  44     };
  45
  46     class SparseArrayValueMap {
  47         typedef HashMap<uint64_t, SparseArrayEntry, WTF::IntHash<uint64_t>, WTF::UnsignedWithZeroKeyHashTraits<uint64_t> > Map;
  48
  49         enum Flags {
  50             Normal = 0,
  51             SparseMode = 1,
  52             LengthIsReadOnly = 2,
  53         };
  54
  55     public:
  56         typedef Map::iterator iterator;
  57         typedef Map::const_iterator const_iterator;
  58         typedef Map::AddResult AddResult;
  59
  60         SparseArrayValueMap()
  61             : m_flags(Normal)
  62             , m_reportedCapacity(0)
  63         {
  64         }
  65
  66         void visitChildren(SlotVisitor&);
  67
  68         bool sparseMode()
  69         {
  70             return m_flags & SparseMode;
  71         }
  72
  73         void setSparseMode()
  74         {
  75             m_flags = static_cast<Flags>(m_flags | SparseMode);
  76         }
  77
  78         bool lengthIsReadOnly()
  79         {
  80             return m_flags & LengthIsReadOnly;
  81         }
  82
  83         void setLengthIsReadOnly()
  84         {
  85             m_flags = static_cast<Flags>(m_flags | LengthIsReadOnly);
  86         }
  87
  88         // These methods may mutate the contents of the map
  89         void put(ExecState*, JSArray*, unsigned, JSValue, bool shouldThrow);
  90         bool putDirect(ExecState*, JSArray*, unsigned, JSValue, bool shouldThrow);
  91         AddResult add(JSArray*, unsigned);
  92         iterator find(unsigned i) { return m_map.find(i); }
  93         // This should ASSERT the remove is valid (check the result of the find).
  94         void remove(iterator it) { m_map.remove(it); }
  95         void remove(unsigned i) { m_map.remove(i); }
  96
  97         // These methods do not mutate the contents of the map.
  98         iterator notFound() { return m_map.end(); }
  99         bool isEmpty() const { return m_map.isEmpty(); }
 100         bool contains(unsigned i) const { return m_map.contains(i); }
 101         size_t size() const { return m_map.size(); }
 102         // Only allow const begin/end iteration.
 103         const_iterator begin() const { return m_map.begin(); }
 104         const_iterator end() const { return m_map.end(); }
 105
 106     private:
 107         Map m_map;
 108         Flags m_flags;
 109         size_t m_reportedCapacity;
 110     };
 111
 112     // This struct holds the actual data values of an array.  A JSArray object points to it's contained ArrayStorage
 113     // struct by pointing to m_vector.  To access the contained ArrayStorage struct, use the getStorage() and
 114     // setStorage() methods.  It is important to note that there may be space before the ArrayStorage that
 115     // is used to quick unshift / shift operation.  The actual allocated pointer is available by using:
 116     //     getStorage() - m_indexBias * sizeof(JSValue)
 117     struct ArrayStorage {
 118         unsigned m_length; // The "length" property on the array
 119         unsigned m_numValuesInVector;
 120         void* m_allocBase; // Pointer to base address returned by malloc().  Keeping this pointer does eliminate false positives from the leak detector.
 121 #if CHECK_ARRAY_CONSISTENCY
 122         // Needs to be a uintptr_t for alignment purposes.
 123         uintptr_t m_initializationIndex;
 124         uintptr_t m_inCompactInitialization;
 125 #else
 126         uintptr_t m_padding;
 127 #endif
 128         WriteBarrier<Unknown> m_vector[1];
 129
 130         static ptrdiff_t lengthOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_length); }
 131         static ptrdiff_t numValuesInVectorOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_numValuesInVector); }
 132         static ptrdiff_t allocBaseOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_allocBase); }
 133         static ptrdiff_t vectorOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_vector); }
 134     };
 135
 136     class JSArray : public JSNonFinalObject {
 137         friend class LLIntOffsetsExtractor;
 138         friend class Walker;
 139         friend class JIT;
 140
 141     protected:
 142         explicit JSArray(JSGlobalData& globalData, Structure* structure)
 143             : JSNonFinalObject(globalData, structure)
 144             , m_indexBias(0)
 145             , m_storage(0)
 146             , m_sparseValueMap(0)
 147         {
 148         }
 149
 150         JS_EXPORT_PRIVATE void finishCreation(JSGlobalData&, unsigned initialLength = 0);
 151         JS_EXPORT_PRIVATE JSArray* tryFinishCreationUninitialized(JSGlobalData&, unsigned initialLength);
 152
 153     public:
 154         typedef JSNonFinalObject Base;
 155
 156         static void finalize(JSCell*);
 157
 158         static JSArray* create(JSGlobalData&, Structure*, unsigned initialLength = 0);
 159
 160         // tryCreateUninitialized is used for fast construction of arrays whose size and
 161         // contents are known at time of creation. Clients of this interface must:
 162         //   - null-check the result (indicating out of memory, or otherwise unable to allocate vector).
 163         //   - call 'initializeIndex' for all properties in sequence, for 0 <= i < initialLength.
 164         //   - called 'completeInitialization' after all properties have been initialized.
 165         static JSArray* tryCreateUninitialized(JSGlobalData&, Structure*, unsigned initialLength);
 166
 167         JS_EXPORT_PRIVATE static bool defineOwnProperty(JSObject*, ExecState*, const Identifier&, PropertyDescriptor&, bool throwException);
 168
 169         static bool getOwnPropertySlot(JSCell*, ExecState*, const Identifier&, PropertySlot&);
 170         JS_EXPORT_PRIVATE static bool getOwnPropertySlotByIndex(JSCell*, ExecState*, unsigned propertyName, PropertySlot&);
 171         static bool getOwnPropertyDescriptor(JSObject*, ExecState*, const Identifier&, PropertyDescriptor&);
 172         static void putByIndex(JSCell*, ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
 173         // This is similar to the JSObject::putDirect* methods:
 174         //  - the prototype chain is not consulted
 175         //  - accessors are not called.
 176         // This method creates a property with attributes writable, enumerable and configurable all set to true.
 177         bool putDirectIndex(ExecState* exec, unsigned propertyName, JSValue value, bool shouldThrow = true)
 178         {
 179             if (canSetIndex(propertyName)) {
 180                 setIndex(exec->globalData(), propertyName, value);
 181                 return true;
 182             }
 183             return putDirectIndexBeyondVectorLength(exec, propertyName, value, shouldThrow);
 184         }
 185
 186         static JS_EXPORTDATA const ClassInfo s_info;
 187
 188         unsigned length() const { return m_storage->m_length; }
 189         // OK to use on new arrays, but not if it might be a RegExpMatchArray.
 190         bool setLength(ExecState*, unsigned, bool throwException = false);
 191
 192         void sort(ExecState*);
 193         void sort(ExecState*, JSValue compareFunction, CallType, const CallData&);
 194         void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&);
 195
 196         void push(ExecState*, JSValue);
 197         JSValue pop(ExecState*);
 198
 199         bool shiftCount(ExecState*, unsigned count);
 200         bool unshiftCount(ExecState*, unsigned count);
 201
 202         bool canGetIndex(unsigned i) { return i < m_vectorLength && m_storage->m_vector[i]; }
 203         JSValue getIndex(unsigned i)
 204         {
 205             ASSERT(canGetIndex(i));
 206             return m_storage->m_vector[i].get();
 207         }
 208
 209         bool canSetIndex(unsigned i) { return i < m_vectorLength; }
 210         void setIndex(JSGlobalData& globalData, unsigned i, JSValue v)
 211         {
 212             ASSERT(canSetIndex(i));
 213
 214             WriteBarrier<Unknown>& x = m_storage->m_vector[i];
 215             if (!x) {
 216                 ArrayStorage *storage = m_storage;
 217                 ++storage->m_numValuesInVector;
 218                 if (i >= storage->m_length)
 219                     storage->m_length = i + 1;
 220             }
 221             x.set(globalData, this, v);
 222         }
 223
 224         inline void initializeIndex(JSGlobalData& globalData, unsigned i, JSValue v)
 225         {
 226             ASSERT(canSetIndex(i));
 227             ArrayStorage *storage = m_storage;
 228 #if CHECK_ARRAY_CONSISTENCY
 229             ASSERT(storage->m_inCompactInitialization);
 230             // Check that we are initializing the next index in sequence.
 231             ASSERT(i == storage->m_initializationIndex);
 232             // tryCreateUninitialized set m_numValuesInVector to the initialLength,
 233             // check we do not try to initialize more than this number of properties.
 234             ASSERT(storage->m_initializationIndex < storage->m_numValuesInVector);
 235             storage->m_initializationIndex++;
 236 #endif
 237             ASSERT(i < storage->m_length);
 238             ASSERT(i < storage->m_numValuesInVector);
 239             storage->m_vector[i].set(globalData, this, v);
 240         }
 241
 242         inline void completeInitialization(unsigned newLength)
 243         {
 244             // Check that we have initialized as meny properties as we think we have.
 245             ASSERT_UNUSED(newLength, newLength == m_storage->m_length);
 246 #if CHECK_ARRAY_CONSISTENCY
 247             // Check that the number of propreties initialized matches the initialLength.
 248             ASSERT(m_storage->m_initializationIndex == m_storage->m_numValuesInVector);
 249             ASSERT(m_storage->m_inCompactInitialization);
 250             m_storage->m_inCompactInitialization = false;
 251 #endif
 252         }
 253
 254         bool hasSparseMap()
 255         {
 256             return m_sparseValueMap;
 257         }
 258
 259         bool inSparseMode()
 260         {
 261             SparseArrayValueMap* map = m_sparseValueMap;
 262             return map && map->sparseMode();
 263         }
 264
 265         void fillArgList(ExecState*, MarkedArgumentBuffer&);
 266         void copyToArguments(ExecState*, CallFrame*, uint32_t length);
 267
 268         static Structure* createStructure(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype)
 269         {
 270             return Structure::create(globalData, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), &s_info);
 271         }
 272
 273         static ptrdiff_t storageOffset()
 274         {
 275             return OBJECT_OFFSETOF(JSArray, m_storage);
 276         }
 277
 278         static ptrdiff_t vectorLengthOffset()
 279         {
 280             return OBJECT_OFFSETOF(JSArray, m_vectorLength);
 281         }
 282
 283         JS_EXPORT_PRIVATE static void visitChildren(JSCell*, SlotVisitor&);
 284
 285         void enterDictionaryMode(JSGlobalData&);
 286
 287     protected:
 288         static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesVisitChildren | OverridesGetPropertyNames | JSObject::StructureFlags;
 289         static void put(JSCell*, ExecState*, const Identifier& propertyName, JSValue, PutPropertySlot&);
 290
 291         static bool deleteProperty(JSCell*, ExecState*, const Identifier& propertyName);
 292         static bool deletePropertyByIndex(JSCell*, ExecState*, unsigned propertyName);
 293         static void getOwnPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
 294
 295         JS_EXPORT_PRIVATE void* subclassData() const;
 296         JS_EXPORT_PRIVATE void setSubclassData(void*);
 297
 298     private:
 299         static size_t storageSize(unsigned vectorLength);
 300         bool isLengthWritable()
 301         {
 302             SparseArrayValueMap* map = m_sparseValueMap;
 303             return !map || !map->lengthIsReadOnly();
 304         }
 305
 306         void setLengthWritable(ExecState*, bool writable);
 307         void putDescriptor(ExecState*, SparseArrayEntry*, PropertyDescriptor&, PropertyDescriptor& old);
 308         bool defineOwnNumericProperty(ExecState*, unsigned, PropertyDescriptor&, bool throwException);
 309         void allocateSparseMap(JSGlobalData&);
 310         void deallocateSparseMap();
 311
 312         bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&);
 313         void putByIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
 314         JS_EXPORT_PRIVATE bool putDirectIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
 315
 316         unsigned getNewVectorLength(unsigned desiredLength);
 317         bool increaseVectorLength(JSGlobalData&, unsigned newLength);
 318         bool unshiftCountSlowCase(JSGlobalData&, unsigned count);
 319
 320         unsigned compactForSorting();
 321
 322         enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck };
 323         void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck);
 324
 325         unsigned m_vectorLength; // The valid length of m_vector
 326         unsigned m_indexBias; // The number of JSValue sized blocks before ArrayStorage.
 327         ArrayStorage *m_storage;
 328
 329         // FIXME: Maybe SparseArrayValueMap should be put into its own JSCell?
 330         SparseArrayValueMap* m_sparseValueMap;
 331
 332         static ptrdiff_t sparseValueMapOffset() { return OBJECT_OFFSETOF(JSArray, m_sparseValueMap); }
 333         static ptrdiff_t indexBiasOffset() { return OBJECT_OFFSETOF(JSArray, m_indexBias); }
 334     };
 335
 336     inline JSArray* JSArray::create(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
 337     {
 338         JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
 339         array->finishCreation(globalData, initialLength);
 340         return array;
 341     }
 342
 343     inline JSArray* JSArray::tryCreateUninitialized(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
 344     {
 345         JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
 346         return array->tryFinishCreationUninitialized(globalData, initialLength);
 347     }
 348
 349     JSArray* asArray(JSValue);
 350
 351     inline JSArray* asArray(JSCell* cell)
 352     {
 353         ASSERT(cell->inherits(&JSArray::s_info));
 354         return jsCast<JSArray*>(cell);
 355     }
 356
 357     inline JSArray* asArray(JSValue value)
 358     {
 359         return asArray(value.asCell());
 360     }
 361
 362     inline bool isJSArray(JSCell* cell) { return cell->classInfo() == &JSArray::s_info; }
 363     inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); }
 364
 365     // Rule from ECMA 15.2 about what an array index is.
 366     // Must exactly match string form of an unsigned integer, and be less than 2^32 - 1.
 367     inline unsigned Identifier::toArrayIndex(bool& ok) const
 368     {
 369         unsigned i = toUInt32(ok);
 370         if (ok && i >= 0xFFFFFFFFU)
 371             ok = false;
 372         return i;
 373     }
 374
 375 // The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
 376 // function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
 377 // size calculation cannot overflow.  (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) +
 378 // (vectorLength * sizeof(WriteBarrier<Unknown>)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
 379 #define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>))
 380
 381 // These values have to be macros to be used in max() and min() without introducing
 382 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
 383 #define MIN_SPARSE_ARRAY_INDEX 10000U
 384 #define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
 385     inline size_t JSArray::storageSize(unsigned vectorLength)
 386     {
 387         ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH);
 388
 389         // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH)
 390         // - as asserted above - the following calculation cannot overflow.
 391         size_t size = (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) + (vectorLength * sizeof(WriteBarrier<Unknown>));
 392         // Assertion to detect integer overflow in previous calculation (should not be possible, provided that
 393         // MAX_STORAGE_VECTOR_LENGTH is correctly defined).
 394         ASSERT(((size - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))));
 395
 396         return size;
 397     }
 398
 399     } // namespace JSC
 400
 401 #endif // JSArray_h