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     typedef HashMap<unsigned, JSValue> SparseArrayValueMap;

    31 

    32     struct ArrayStorage {

    33         unsigned m_length;

    34         unsigned m_numValuesInVector;

    35         SparseArrayValueMap* m_sparseValueMap;

    36         void* subclassData; // A JSArray subclass can use this to fill the vector lazily.

    37         size_t reportedMapCapacity;

    38 #if CHECK_ARRAY_CONSISTENCY

    39         bool m_inCompactInitialization;

    40 #endif

    41         JSValue m_vector[1];

    42     };

    43 

    44     // The CreateCompact creation mode is used for fast construction of arrays

    45     // whose size and contents are known at time of creation.

    46     //

    47     // There are two obligations when using this mode:

    48     //

    49     //   - uncheckedSetIndex() must be used when initializing the array.

    50     //   - setLength() must be called after initialization.

    51 

    52     enum ArrayCreationMode { CreateCompact, CreateInitialized };

    53 

    54     class JSArray : public JSObject {

    55         friend class JIT;

    56         friend class Walker;

    57 

    58     public:

    59         explicit JSArray(NonNullPassRefPtr<Structure>);

    60         JSArray(NonNullPassRefPtr<Structure>, unsigned initialLength, ArrayCreationMode);

    61         JSArray(NonNullPassRefPtr<Structure>, const ArgList& initialValues);

    62         virtual ~JSArray();

    63 

    64         virtual bool getOwnPropertySlot(ExecState*, const Identifier& propertyName, PropertySlot&);

    65         virtual bool getOwnPropertySlot(ExecState*, unsigned propertyName, PropertySlot&);

    66         virtual bool getOwnPropertyDescriptor(ExecState*, const Identifier&, PropertyDescriptor&);

    67         virtual void put(ExecState*, unsigned propertyName, JSValue); // FIXME: Make protected and add setItem.

    68 

    69         static JS_EXPORTDATA const ClassInfo info;

    70 

    71         unsigned length() const { return m_storage->m_length; }

    72         void setLength(unsigned); // OK to use on new arrays, but not if it might be a RegExpMatchArray.

    73 

    74         void sort(ExecState*);

    75         void sort(ExecState*, JSValue compareFunction, CallType, const CallData&);

    76         void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&);

    77 

    78         void push(ExecState*, JSValue);

    79         JSValue pop();

    80 

    81         bool canGetIndex(unsigned i) { return i < m_vectorLength && m_storage->m_vector[i]; }

    82         JSValue getIndex(unsigned i)

    83         {

    84             ASSERT(canGetIndex(i));

    85             return m_storage->m_vector[i];

    86         }

    87 

    88         bool canSetIndex(unsigned i) { return i < m_vectorLength; }

    89         void setIndex(unsigned i, JSValue v)

    90         {

    91             ASSERT(canSetIndex(i));

    92             JSValue& x = m_storage->m_vector[i];

    93             if (!x) {

    94                 ++m_storage->m_numValuesInVector;

    95                 if (i >= m_storage->m_length)

    96                     m_storage->m_length = i + 1;

    97             }

    98             x = v;

    99         }

   100 

   101         void uncheckedSetIndex(unsigned i, JSValue v)

   102         {

   103             ASSERT(canSetIndex(i));

   104 #if CHECK_ARRAY_CONSISTENCY

   105             ASSERT(m_storage->m_inCompactInitialization);

   106 #endif

   107             m_storage->m_vector[i] = v;

   108         }

   109 

   110         void fillArgList(ExecState*, MarkedArgumentBuffer&);

   111         void copyToRegisters(ExecState*, Register*, uint32_t);

   112 

   113         static PassRefPtr<Structure> createStructure(JSValue prototype)

   114         {

   115             return Structure::create(prototype, TypeInfo(ObjectType, StructureFlags), AnonymousSlotCount);

   116         }

   117         

   118         inline void markChildrenDirect(MarkStack& markStack);

   119 

   120     protected:

   121         static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesMarkChildren | OverridesGetPropertyNames | JSObject::StructureFlags;

   122         virtual void put(ExecState*, const Identifier& propertyName, JSValue, PutPropertySlot&);

   123         virtual bool deleteProperty(ExecState*, const Identifier& propertyName);

   124         virtual bool deleteProperty(ExecState*, unsigned propertyName);

   125         virtual void getOwnPropertyNames(ExecState*, PropertyNameArray&, EnumerationMode mode = ExcludeDontEnumProperties);

   126         virtual void markChildren(MarkStack&);

   127 

   128         void* subclassData() const;

   129         void setSubclassData(void*);

   130 

   131     private:

   132         virtual const ClassInfo* classInfo() const { return &info; }

   133 

   134         bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&);

   135         void putSlowCase(ExecState*, unsigned propertyName, JSValue);

   136 

   137         bool increaseVectorLength(unsigned newLength);

   138         

   139         unsigned compactForSorting();

   140 

   141         enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck };

   142         void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck);

   143 

   144         unsigned m_vectorLength;

   145         ArrayStorage* m_storage;

   146     };

   147 

   148     JSArray* asArray(JSValue);

   149 

   150     inline JSArray* asArray(JSCell* cell)

   151     {

   152         ASSERT(cell->inherits(&JSArray::info));

   153         return static_cast<JSArray*>(cell);

   154     }

   155 

   156     inline JSArray* asArray(JSValue value)

   157     {

   158         return asArray(value.asCell());

   159     }

   160 

   161     inline bool isJSArray(JSGlobalData* globalData, JSValue v)

   162     {

   163         return v.isCell() && v.asCell()->vptr() == globalData->jsArrayVPtr;

   164     }

   165     inline bool isJSArray(JSGlobalData* globalData, JSCell* cell) { return cell->vptr() == globalData->jsArrayVPtr; }

   166 

   167     inline void JSArray::markChildrenDirect(MarkStack& markStack)

   168     {

   169         JSObject::markChildrenDirect(markStack);

   170         

   171         ArrayStorage* storage = m_storage;

   172 

   173         unsigned usedVectorLength = std::min(storage->m_length, m_vectorLength);

   174         markStack.appendValues(storage->m_vector, usedVectorLength, MayContainNullValues);

   175 

   176         if (SparseArrayValueMap* map = storage->m_sparseValueMap) {

   177             SparseArrayValueMap::iterator end = map->end();

   178             for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)

   179                 markStack.append(it->second);

   180         }

   181     }

   182 

   183     inline void MarkStack::markChildren(JSCell* cell)

   184     {

   185         ASSERT(Heap::isCellMarked(cell));

   186         if (!cell->structure()->typeInfo().overridesMarkChildren()) {

   187 #ifdef NDEBUG

   188             asObject(cell)->markChildrenDirect(*this);

   189 #else

   190             ASSERT(!m_isCheckingForDefaultMarkViolation);

   191             m_isCheckingForDefaultMarkViolation = true;

   192             cell->markChildren(*this);

   193             ASSERT(m_isCheckingForDefaultMarkViolation);

   194             m_isCheckingForDefaultMarkViolation = false;

   195 #endif

   196             return;

   197         }

   198         if (cell->vptr() == m_jsArrayVPtr) {

   199             asArray(cell)->markChildrenDirect(*this);

   200             return;

   201         }

   202         cell->markChildren(*this);

   203     }

   204 

   205     inline void MarkStack::drain()

   206     {

   207         while (!m_markSets.isEmpty() || !m_values.isEmpty()) {

   208             while (!m_markSets.isEmpty() && m_values.size() < 50) {

   209                 ASSERT(!m_markSets.isEmpty());

   210                 MarkSet& current = m_markSets.last();

   211                 ASSERT(current.m_values);

   212                 JSValue* end = current.m_end;

   213                 ASSERT(current.m_values);

   214                 ASSERT(current.m_values != end);

   215             findNextUnmarkedNullValue:

   216                 ASSERT(current.m_values != end);

   217                 JSValue value = *current.m_values;

   218                 current.m_values++;

   219 

   220                 JSCell* cell;

   221                 if (!value || !value.isCell() || Heap::isCellMarked(cell = value.asCell())) {

   222                     if (current.m_values == end) {

   223                         m_markSets.removeLast();

   224                         continue;

   225                     }

   226                     goto findNextUnmarkedNullValue;

   227                 }

   228 

   229                 Heap::markCell(cell);

   230                 if (cell->structure()->typeInfo().type() < CompoundType) {

   231                     if (current.m_values == end) {

   232                         m_markSets.removeLast();

   233                         continue;

   234                     }

   235                     goto findNextUnmarkedNullValue;

   236                 }

   237 

   238                 if (current.m_values == end)

   239                     m_markSets.removeLast();

   240 

   241                 markChildren(cell);

   242             }

   243             while (!m_values.isEmpty())

   244                 markChildren(m_values.removeLast());

   245         }

   246     }

   247     

   248 } // namespace JSC

   249 

   250 #endif // JSArray_h