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