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 namespace JSC {
  27
  28     typedef HashMap<unsigned, JSValue> SparseArrayValueMap;
  29
  30     struct ArrayStorage {
  31         unsigned m_length;
  32         unsigned m_numValuesInVector;
  33         SparseArrayValueMap* m_sparseValueMap;
  34         void* subclassData; // A JSArray subclass can use this to fill the vector lazily.
  35         size_t reportedMapCapacity;
  36         JSValue m_vector[1];
  37     };
  38
  39     class JSArray : public JSObject {
  40         friend class JIT;
  41         friend class Walker;
  42
  43     public:
  44         explicit JSArray(NonNullPassRefPtr<Structure>);
  45         JSArray(NonNullPassRefPtr<Structure>, unsigned initialLength);
  46         JSArray(NonNullPassRefPtr<Structure>, const ArgList& initialValues);
  47         virtual ~JSArray();
  48
  49         virtual bool getOwnPropertySlot(ExecState*, const Identifier& propertyName, PropertySlot&);
  50         virtual bool getOwnPropertySlot(ExecState*, unsigned propertyName, PropertySlot&);
  51         virtual bool getOwnPropertyDescriptor(ExecState*, const Identifier&, PropertyDescriptor&);
  52         virtual void put(ExecState*, unsigned propertyName, JSValue); // FIXME: Make protected and add setItem.
  53
  54         static JS_EXPORTDATA const ClassInfo info;
  55
  56         unsigned length() const { return m_storage->m_length; }
  57         void setLength(unsigned); // OK to use on new arrays, but not if it might be a RegExpMatchArray.
  58
  59         void sort(ExecState*);
  60         void sort(ExecState*, JSValue compareFunction, CallType, const CallData&);
  61         void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&);
  62
  63         void push(ExecState*, JSValue);
  64         JSValue pop();
  65
  66         bool canGetIndex(unsigned i) { return i < m_vectorLength && m_storage->m_vector[i]; }
  67         JSValue getIndex(unsigned i)
  68         {
  69             ASSERT(canGetIndex(i));
  70             return m_storage->m_vector[i];
  71         }
  72
  73         bool canSetIndex(unsigned i) { return i < m_vectorLength; }
  74         void setIndex(unsigned i, JSValue v)
  75         {
  76             ASSERT(canSetIndex(i));
  77             JSValue& x = m_storage->m_vector[i];
  78             if (!x) {
  79                 ++m_storage->m_numValuesInVector;
  80                 if (i >= m_storage->m_length)
  81                     m_storage->m_length = i + 1;
  82             }
  83             x = v;
  84         }
  85
  86         void fillArgList(ExecState*, MarkedArgumentBuffer&);
  87         void copyToRegisters(ExecState*, Register*, uint32_t);
  88
  89         static PassRefPtr<Structure> createStructure(JSValue prototype)
  90         {
  91             return Structure::create(prototype, TypeInfo(ObjectType, StructureFlags), AnonymousSlotCount);
  92         }
  93
  94         inline void markChildrenDirect(MarkStack& markStack);
  95
  96     protected:
  97         static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesMarkChildren | OverridesGetPropertyNames | JSObject::StructureFlags;
  98         virtual void put(ExecState*, const Identifier& propertyName, JSValue, PutPropertySlot&);
  99         virtual bool deleteProperty(ExecState*, const Identifier& propertyName);
 100         virtual bool deleteProperty(ExecState*, unsigned propertyName);
 101         virtual void getOwnPropertyNames(ExecState*, PropertyNameArray&, EnumerationMode mode = ExcludeDontEnumProperties);
 102         virtual void markChildren(MarkStack&);
 103
 104         void* subclassData() const;
 105         void setSubclassData(void*);
 106
 107     private:
 108         virtual const ClassInfo* classInfo() const { return &info; }
 109
 110         bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&);
 111         void putSlowCase(ExecState*, unsigned propertyName, JSValue);
 112
 113         bool increaseVectorLength(unsigned newLength);
 114
 115         unsigned compactForSorting();
 116
 117         enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck };
 118         void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck);
 119
 120         unsigned m_vectorLength;
 121         ArrayStorage* m_storage;
 122     };
 123
 124     JSArray* asArray(JSValue);
 125
 126     inline JSArray* asArray(JSCell* cell)
 127     {
 128         ASSERT(cell->inherits(&JSArray::info));
 129         return static_cast<JSArray*>(cell);
 130     }
 131
 132     inline JSArray* asArray(JSValue value)
 133     {
 134         return asArray(value.asCell());
 135     }
 136
 137     inline bool isJSArray(JSGlobalData* globalData, JSValue v)
 138     {
 139         return v.isCell() && v.asCell()->vptr() == globalData->jsArrayVPtr;
 140     }
 141     inline bool isJSArray(JSGlobalData* globalData, JSCell* cell) { return cell->vptr() == globalData->jsArrayVPtr; }
 142
 143     inline void JSArray::markChildrenDirect(MarkStack& markStack)
 144     {
 145         JSObject::markChildrenDirect(markStack);
 146
 147         ArrayStorage* storage = m_storage;
 148
 149         unsigned usedVectorLength = std::min(storage->m_length, m_vectorLength);
 150         markStack.appendValues(storage->m_vector, usedVectorLength, MayContainNullValues);
 151
 152         if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
 153             SparseArrayValueMap::iterator end = map->end();
 154             for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
 155                 markStack.append(it->second);
 156         }
 157     }
 158
 159     inline void MarkStack::markChildren(JSCell* cell)
 160     {
 161         ASSERT(Heap::isCellMarked(cell));
 162         if (!cell->structure()->typeInfo().overridesMarkChildren()) {
 163 #ifdef NDEBUG
 164             asObject(cell)->markChildrenDirect(*this);
 165 #else
 166             ASSERT(!m_isCheckingForDefaultMarkViolation);
 167             m_isCheckingForDefaultMarkViolation = true;
 168             cell->markChildren(*this);
 169             ASSERT(m_isCheckingForDefaultMarkViolation);
 170             m_isCheckingForDefaultMarkViolation = false;
 171 #endif
 172             return;
 173         }
 174         if (cell->vptr() == m_jsArrayVPtr) {
 175             asArray(cell)->markChildrenDirect(*this);
 176             return;
 177         }
 178         cell->markChildren(*this);
 179     }
 180
 181     inline void MarkStack::drain()
 182     {
 183         while (!m_markSets.isEmpty() || !m_values.isEmpty()) {
 184             while (!m_markSets.isEmpty() && m_values.size() < 50) {
 185                 ASSERT(!m_markSets.isEmpty());
 186                 MarkSet& current = m_markSets.last();
 187                 ASSERT(current.m_values);
 188                 JSValue* end = current.m_end;
 189                 ASSERT(current.m_values);
 190                 ASSERT(current.m_values != end);
 191             findNextUnmarkedNullValue:
 192                 ASSERT(current.m_values != end);
 193                 JSValue value = *current.m_values;
 194                 current.m_values++;
 195
 196                 JSCell* cell;
 197                 if (!value || !value.isCell() || Heap::isCellMarked(cell = value.asCell())) {
 198                     if (current.m_values == end) {
 199                         m_markSets.removeLast();
 200                         continue;
 201                     }
 202                     goto findNextUnmarkedNullValue;
 203                 }
 204
 205                 Heap::markCell(cell);
 206                 if (cell->structure()->typeInfo().type() < CompoundType) {
 207                     if (current.m_values == end) {
 208                         m_markSets.removeLast();
 209                         continue;
 210                     }
 211                     goto findNextUnmarkedNullValue;
 212                 }
 213
 214                 if (current.m_values == end)
 215                     m_markSets.removeLast();
 216
 217                 markChildren(cell);
 218             }
 219             while (!m_values.isEmpty())
 220                 markChildren(m_values.removeLast());
 221         }
 222     }
 223
 224 } // namespace JSC
 225
 226 #endif // JSArray_h