1 /* 2 * Copyright (C) 1999-2000 Harri Porten (porten (at) 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 typedef HashMap<unsigned, WriteBarrier<Unknown> > SparseArrayValueMap; 31 32 // This struct holds the actual data values of an array. A JSArray object points to it's contained ArrayStorage 33 // struct by pointing to m_vector. To access the contained ArrayStorage struct, use the getStorage() and 34 // setStorage() methods. It is important to note that there may be space before the ArrayStorage that 35 // is used to quick unshift / shift operation. The actual allocated pointer is available by using: 36 // getStorage() - m_indexBias * sizeof(JSValue) 37 struct ArrayStorage { 38 unsigned m_length; // The "length" property on the array 39 unsigned m_numValuesInVector; 40 SparseArrayValueMap* m_sparseValueMap; 41 void* subclassData; // A JSArray subclass can use this to fill the vector lazily. 42 void* m_allocBase; // Pointer to base address returned by malloc(). Keeping this pointer does eliminate false positives from the leak detector. 43 size_t reportedMapCapacity; 44 #if CHECK_ARRAY_CONSISTENCY 45 bool m_inCompactInitialization; 46 #endif 47 WriteBarrier<Unknown> m_vector[1]; 48 }; 49 50 // The CreateCompact creation mode is used for fast construction of arrays 51 // whose size and contents are known at time of creation. 52 // 53 // There are two obligations when using this mode: 54 // 55 // - uncheckedSetIndex() must be used when initializing the array. 56 // - setLength() must be called after initialization. 57 58 enum ArrayCreationMode { CreateCompact, CreateInitialized }; 59 60 class JSArray : public JSNonFinalObject { 61 friend class Walker; 62 63 public: 64 JSArray(VPtrStealingHackType); 65 66 explicit JSArray(JSGlobalData&, Structure*); 67 JSArray(JSGlobalData&, Structure*, unsigned initialLength, ArrayCreationMode); 68 JSArray(JSGlobalData&, Structure*, const ArgList& initialValues); 69 virtual ~JSArray(); 70 71 virtual bool getOwnPropertySlot(ExecState*, const Identifier& propertyName, PropertySlot&); 72 virtual bool getOwnPropertySlot(ExecState*, unsigned propertyName, PropertySlot&); 73 virtual bool getOwnPropertyDescriptor(ExecState*, const Identifier&, PropertyDescriptor&); 74 virtual void put(ExecState*, unsigned propertyName, JSValue); // FIXME: Make protected and add setItem. 75 76 static JS_EXPORTDATA const ClassInfo s_info; 77 78 unsigned length() const { return m_storage->m_length; } 79 void setLength(unsigned); // OK to use on new arrays, but not if it might be a RegExpMatchArray. 80 81 void sort(ExecState*); 82 void sort(ExecState*, JSValue compareFunction, CallType, const CallData&); 83 void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&); 84 85 void push(ExecState*, JSValue); 86 JSValue pop(); 87 88 void shiftCount(ExecState*, int count); 89 void unshiftCount(ExecState*, int count); 90 91 bool canGetIndex(unsigned i) { return i < m_vectorLength && m_storage->m_vector[i]; } 92 JSValue getIndex(unsigned i) 93 { 94 ASSERT(canGetIndex(i)); 95 return m_storage->m_vector[i].get(); 96 } 97 98 bool canSetIndex(unsigned i) { return i < m_vectorLength; } 99 void setIndex(JSGlobalData& globalData, unsigned i, JSValue v) 100 { 101 ASSERT(canSetIndex(i)); 102 103 WriteBarrier<Unknown>& x = m_storage->m_vector[i]; 104 if (!x) { 105 ArrayStorage *storage = m_storage; 106 ++storage->m_numValuesInVector; 107 if (i >= storage->m_length) 108 storage->m_length = i + 1; 109 } 110 x.set(globalData, this, v); 111 } 112 113 void uncheckedSetIndex(JSGlobalData& globalData, unsigned i, JSValue v) 114 { 115 ASSERT(canSetIndex(i)); 116 ArrayStorage *storage = m_storage; 117 #if CHECK_ARRAY_CONSISTENCY 118 ASSERT(storage->m_inCompactInitialization); 119 #endif 120 storage->m_vector[i].set(globalData, this, v); 121 } 122 123 void fillArgList(ExecState*, MarkedArgumentBuffer&); 124 void copyToRegisters(ExecState*, Register*, uint32_t); 125 126 static Structure* createStructure(JSGlobalData& globalData, JSValue prototype) 127 { 128 return Structure::create(globalData, prototype, TypeInfo(ObjectType, StructureFlags), AnonymousSlotCount, &s_info); 129 } 130 131 inline void markChildrenDirect(MarkStack& markStack); 132 133 static ptrdiff_t storageOffset() 134 { 135 return OBJECT_OFFSETOF(JSArray, m_storage); 136 } 137 138 static ptrdiff_t vectorLengthOffset() 139 { 140 return OBJECT_OFFSETOF(JSArray, m_vectorLength); 141 } 142 143 protected: 144 static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesMarkChildren | OverridesGetPropertyNames | JSObject::StructureFlags; 145 virtual void put(ExecState*, const Identifier& propertyName, JSValue, PutPropertySlot&); 146 virtual bool deleteProperty(ExecState*, const Identifier& propertyName); 147 virtual bool deleteProperty(ExecState*, unsigned propertyName); 148 virtual void getOwnPropertyNames(ExecState*, PropertyNameArray&, EnumerationMode mode = ExcludeDontEnumProperties); 149 virtual void markChildren(MarkStack&); 150 151 void* subclassData() const; 152 void setSubclassData(void*); 153 154 private: 155 bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&); 156 void putSlowCase(ExecState*, unsigned propertyName, JSValue); 157 158 unsigned getNewVectorLength(unsigned desiredLength); 159 bool increaseVectorLength(unsigned newLength); 160 bool increaseVectorPrefixLength(unsigned newLength); 161 162 unsigned compactForSorting(); 163 164 enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck }; 165 void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck); 166 167 unsigned m_vectorLength; // The valid length of m_vector 168 int m_indexBias; // The number of JSValue sized blocks before ArrayStorage. 169 ArrayStorage *m_storage; 170 }; 171 172 JSArray* asArray(JSValue); 173 174 inline JSArray* asArray(JSCell* cell) 175 { 176 ASSERT(cell->inherits(&JSArray::s_info)); 177 return static_cast<JSArray*>(cell); 178 } 179 180 inline JSArray* asArray(JSValue value) 181 { 182 return asArray(value.asCell()); 183 } 184 185 inline bool isJSArray(JSGlobalData* globalData, JSCell* cell) { return cell->vptr() == globalData->jsArrayVPtr; } 186 inline bool isJSArray(JSGlobalData* globalData, JSValue v) { return v.isCell() && isJSArray(globalData, v.asCell()); } 187 188 inline void JSArray::markChildrenDirect(MarkStack& markStack) 189 { 190 JSObject::markChildrenDirect(markStack); 191 192 ArrayStorage* storage = m_storage; 193 194 unsigned usedVectorLength = std::min(storage->m_length, m_vectorLength); 195 markStack.appendValues(storage->m_vector, usedVectorLength, MayContainNullValues); 196 197 if (SparseArrayValueMap* map = storage->m_sparseValueMap) { 198 SparseArrayValueMap::iterator end = map->end(); 199 for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) 200 markStack.append(&it->second); 201 } 202 } 203 204 // Rule from ECMA 15.2 about what an array index is. 205 // Must exactly match string form of an unsigned integer, and be less than 2^32 - 1. 206 inline unsigned Identifier::toArrayIndex(bool& ok) const 207 { 208 unsigned i = toUInt32(ok); 209 if (ok && i >= 0xFFFFFFFFU) 210 ok = false; 211 return i; 212 } 213 214 } // namespace JSC 215 216 #endif // JSArray_h 217
