#include "JSObject.h"
+#define CHECK_ARRAY_CONSISTENCY 0
+
namespace JSC {
- typedef HashMap<unsigned, JSValue> SparseArrayValueMap;
+ class JSArray;
+ class LLIntOffsetsExtractor;
+
+ struct SparseArrayEntry : public WriteBarrier<Unknown> {
+ typedef WriteBarrier<Unknown> Base;
+
+ SparseArrayEntry() : attributes(0) {}
+
+ JSValue get(ExecState*, JSArray*) const;
+ void get(PropertySlot&) const;
+ void get(PropertyDescriptor&) const;
+ JSValue getNonSparseMode() const;
+
+ unsigned attributes;
+ };
+
+ class SparseArrayValueMap {
+ typedef HashMap<uint64_t, SparseArrayEntry, WTF::IntHash<uint64_t>, WTF::UnsignedWithZeroKeyHashTraits<uint64_t> > Map;
+
+ enum Flags {
+ Normal = 0,
+ SparseMode = 1,
+ LengthIsReadOnly = 2,
+ };
+
+ public:
+ typedef Map::iterator iterator;
+ typedef Map::const_iterator const_iterator;
+ typedef Map::AddResult AddResult;
+
+ SparseArrayValueMap()
+ : m_flags(Normal)
+ , m_reportedCapacity(0)
+ {
+ }
+
+ void visitChildren(SlotVisitor&);
+
+ bool sparseMode()
+ {
+ return m_flags & SparseMode;
+ }
+
+ void setSparseMode()
+ {
+ m_flags = static_cast<Flags>(m_flags | SparseMode);
+ }
+
+ bool lengthIsReadOnly()
+ {
+ return m_flags & LengthIsReadOnly;
+ }
+
+ void setLengthIsReadOnly()
+ {
+ m_flags = static_cast<Flags>(m_flags | LengthIsReadOnly);
+ }
+
+ // These methods may mutate the contents of the map
+ void put(ExecState*, JSArray*, unsigned, JSValue, bool shouldThrow);
+ bool putDirect(ExecState*, JSArray*, unsigned, JSValue, bool shouldThrow);
+ AddResult add(JSArray*, unsigned);
+ iterator find(unsigned i) { return m_map.find(i); }
+ // This should ASSERT the remove is valid (check the result of the find).
+ void remove(iterator it) { m_map.remove(it); }
+ void remove(unsigned i) { m_map.remove(i); }
+
+ // These methods do not mutate the contents of the map.
+ iterator notFound() { return m_map.end(); }
+ bool isEmpty() const { return m_map.isEmpty(); }
+ bool contains(unsigned i) const { return m_map.contains(i); }
+ size_t size() const { return m_map.size(); }
+ // Only allow const begin/end iteration.
+ const_iterator begin() const { return m_map.begin(); }
+ const_iterator end() const { return m_map.end(); }
+ private:
+ Map m_map;
+ Flags m_flags;
+ size_t m_reportedCapacity;
+ };
+
+ // This struct holds the actual data values of an array. A JSArray object points to it's contained ArrayStorage
+ // struct by pointing to m_vector. To access the contained ArrayStorage struct, use the getStorage() and
+ // setStorage() methods. It is important to note that there may be space before the ArrayStorage that
+ // is used to quick unshift / shift operation. The actual allocated pointer is available by using:
+ // getStorage() - m_indexBias * sizeof(JSValue)
struct ArrayStorage {
- unsigned m_length;
+ unsigned m_length; // The "length" property on the array
unsigned m_numValuesInVector;
- SparseArrayValueMap* m_sparseValueMap;
- void* lazyCreationData; // A JSArray subclass can use this to fill the vector lazily.
- size_t reportedMapCapacity;
- JSValue m_vector[1];
+ void* m_allocBase; // Pointer to base address returned by malloc(). Keeping this pointer does eliminate false positives from the leak detector.
+#if CHECK_ARRAY_CONSISTENCY
+ // Needs to be a uintptr_t for alignment purposes.
+ uintptr_t m_initializationIndex;
+ uintptr_t m_inCompactInitialization;
+#else
+ uintptr_t m_padding;
+#endif
+ WriteBarrier<Unknown> m_vector[1];
+
+ static ptrdiff_t lengthOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_length); }
+ static ptrdiff_t numValuesInVectorOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_numValuesInVector); }
+ static ptrdiff_t allocBaseOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_allocBase); }
+ static ptrdiff_t vectorOffset() { return OBJECT_OFFSETOF(ArrayStorage, m_vector); }
};
- class JSArray : public JSObject {
- friend class JIT;
+ class JSArray : public JSNonFinalObject {
+ friend class LLIntOffsetsExtractor;
friend class Walker;
+ friend class JIT;
- public:
- explicit JSArray(NonNullPassRefPtr<Structure>);
- JSArray(NonNullPassRefPtr<Structure>, unsigned initialLength);
- JSArray(NonNullPassRefPtr<Structure>, const ArgList& initialValues);
- virtual ~JSArray();
-
- virtual bool getOwnPropertySlot(ExecState*, const Identifier& propertyName, PropertySlot&);
- virtual bool getOwnPropertySlot(ExecState*, unsigned propertyName, PropertySlot&);
- virtual bool getOwnPropertyDescriptor(ExecState*, const Identifier&, PropertyDescriptor&);
- virtual void put(ExecState*, unsigned propertyName, JSValue); // FIXME: Make protected and add setItem.
+ protected:
+ explicit JSArray(JSGlobalData& globalData, Structure* structure)
+ : JSNonFinalObject(globalData, structure)
+ , m_indexBias(0)
+ , m_storage(0)
+ , m_sparseValueMap(0)
+ {
+ }
- static JS_EXPORTDATA const ClassInfo info;
+ JS_EXPORT_PRIVATE void finishCreation(JSGlobalData&, unsigned initialLength = 0);
+ JS_EXPORT_PRIVATE JSArray* tryFinishCreationUninitialized(JSGlobalData&, unsigned initialLength);
+
+ public:
+ typedef JSNonFinalObject Base;
+
+ static void finalize(JSCell*);
+
+ static JSArray* create(JSGlobalData&, Structure*, unsigned initialLength = 0);
+
+ // tryCreateUninitialized is used for fast construction of arrays whose size and
+ // contents are known at time of creation. Clients of this interface must:
+ // - null-check the result (indicating out of memory, or otherwise unable to allocate vector).
+ // - call 'initializeIndex' for all properties in sequence, for 0 <= i < initialLength.
+ // - called 'completeInitialization' after all properties have been initialized.
+ static JSArray* tryCreateUninitialized(JSGlobalData&, Structure*, unsigned initialLength);
+
+ JS_EXPORT_PRIVATE static bool defineOwnProperty(JSObject*, ExecState*, const Identifier&, PropertyDescriptor&, bool throwException);
+
+ static bool getOwnPropertySlot(JSCell*, ExecState*, const Identifier&, PropertySlot&);
+ JS_EXPORT_PRIVATE static bool getOwnPropertySlotByIndex(JSCell*, ExecState*, unsigned propertyName, PropertySlot&);
+ static bool getOwnPropertyDescriptor(JSObject*, ExecState*, const Identifier&, PropertyDescriptor&);
+ static void putByIndex(JSCell*, ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
+ // This is similar to the JSObject::putDirect* methods:
+ // - the prototype chain is not consulted
+ // - accessors are not called.
+ // This method creates a property with attributes writable, enumerable and configurable all set to true.
+ bool putDirectIndex(ExecState* exec, unsigned propertyName, JSValue value, bool shouldThrow = true)
+ {
+ if (canSetIndex(propertyName)) {
+ setIndex(exec->globalData(), propertyName, value);
+ return true;
+ }
+ return putDirectIndexBeyondVectorLength(exec, propertyName, value, shouldThrow);
+ }
+ static JS_EXPORTDATA const ClassInfo s_info;
+
unsigned length() const { return m_storage->m_length; }
- void setLength(unsigned); // OK to use on new arrays, but not if it might be a RegExpMatchArray.
+ // OK to use on new arrays, but not if it might be a RegExpMatchArray.
+ bool setLength(ExecState*, unsigned, bool throwException = false);
void sort(ExecState*);
void sort(ExecState*, JSValue compareFunction, CallType, const CallData&);
void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&);
void push(ExecState*, JSValue);
- JSValue pop();
+ JSValue pop(ExecState*);
+
+ bool shiftCount(ExecState*, unsigned count);
+ bool unshiftCount(ExecState*, unsigned count);
bool canGetIndex(unsigned i) { return i < m_vectorLength && m_storage->m_vector[i]; }
JSValue getIndex(unsigned i)
{
ASSERT(canGetIndex(i));
- return m_storage->m_vector[i];
+ return m_storage->m_vector[i].get();
}
bool canSetIndex(unsigned i) { return i < m_vectorLength; }
- void setIndex(unsigned i, JSValue v)
+ void setIndex(JSGlobalData& globalData, unsigned i, JSValue v)
{
ASSERT(canSetIndex(i));
- JSValue& x = m_storage->m_vector[i];
+
+ WriteBarrier<Unknown>& x = m_storage->m_vector[i];
if (!x) {
- ++m_storage->m_numValuesInVector;
- if (i >= m_storage->m_length)
- m_storage->m_length = i + 1;
+ ArrayStorage *storage = m_storage;
+ ++storage->m_numValuesInVector;
+ if (i >= storage->m_length)
+ storage->m_length = i + 1;
}
- x = v;
+ x.set(globalData, this, v);
+ }
+
+ inline void initializeIndex(JSGlobalData& globalData, unsigned i, JSValue v)
+ {
+ ASSERT(canSetIndex(i));
+ ArrayStorage *storage = m_storage;
+#if CHECK_ARRAY_CONSISTENCY
+ ASSERT(storage->m_inCompactInitialization);
+ // Check that we are initializing the next index in sequence.
+ ASSERT(i == storage->m_initializationIndex);
+ // tryCreateUninitialized set m_numValuesInVector to the initialLength,
+ // check we do not try to initialize more than this number of properties.
+ ASSERT(storage->m_initializationIndex < storage->m_numValuesInVector);
+ storage->m_initializationIndex++;
+#endif
+ ASSERT(i < storage->m_length);
+ ASSERT(i < storage->m_numValuesInVector);
+ storage->m_vector[i].set(globalData, this, v);
+ }
+
+ inline void completeInitialization(unsigned newLength)
+ {
+ // Check that we have initialized as meny properties as we think we have.
+ ASSERT_UNUSED(newLength, newLength == m_storage->m_length);
+#if CHECK_ARRAY_CONSISTENCY
+ // Check that the number of propreties initialized matches the initialLength.
+ ASSERT(m_storage->m_initializationIndex == m_storage->m_numValuesInVector);
+ ASSERT(m_storage->m_inCompactInitialization);
+ m_storage->m_inCompactInitialization = false;
+#endif
+ }
+
+ bool hasSparseMap()
+ {
+ return m_sparseValueMap;
+ }
+
+ bool inSparseMode()
+ {
+ SparseArrayValueMap* map = m_sparseValueMap;
+ return map && map->sparseMode();
}
void fillArgList(ExecState*, MarkedArgumentBuffer&);
- void copyToRegisters(ExecState*, Register*, uint32_t);
+ void copyToArguments(ExecState*, CallFrame*, uint32_t length);
- static PassRefPtr<Structure> createStructure(JSValue prototype)
+ static Structure* createStructure(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype)
{
- return Structure::create(prototype, TypeInfo(ObjectType, StructureFlags), AnonymousSlotCount);
+ return Structure::create(globalData, globalObject, prototype, TypeInfo(ObjectType, StructureFlags), &s_info);
}
- inline void markChildrenDirect(MarkStack& markStack);
+ static ptrdiff_t storageOffset()
+ {
+ return OBJECT_OFFSETOF(JSArray, m_storage);
+ }
+
+ static ptrdiff_t vectorLengthOffset()
+ {
+ return OBJECT_OFFSETOF(JSArray, m_vectorLength);
+ }
+
+ JS_EXPORT_PRIVATE static void visitChildren(JSCell*, SlotVisitor&);
+
+ void enterDictionaryMode(JSGlobalData&);
protected:
- static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesMarkChildren | OverridesGetPropertyNames | JSObject::StructureFlags;
- virtual void put(ExecState*, const Identifier& propertyName, JSValue, PutPropertySlot&);
- virtual bool deleteProperty(ExecState*, const Identifier& propertyName);
- virtual bool deleteProperty(ExecState*, unsigned propertyName);
- virtual void getOwnPropertyNames(ExecState*, PropertyNameArray&, EnumerationMode mode = ExcludeDontEnumProperties);
- virtual void markChildren(MarkStack&);
+ static const unsigned StructureFlags = OverridesGetOwnPropertySlot | OverridesVisitChildren | OverridesGetPropertyNames | JSObject::StructureFlags;
+ static void put(JSCell*, ExecState*, const Identifier& propertyName, JSValue, PutPropertySlot&);
+
+ static bool deleteProperty(JSCell*, ExecState*, const Identifier& propertyName);
+ static bool deletePropertyByIndex(JSCell*, ExecState*, unsigned propertyName);
+ static void getOwnPropertyNames(JSObject*, ExecState*, PropertyNameArray&, EnumerationMode);
- void* lazyCreationData();
- void setLazyCreationData(void*);
+ JS_EXPORT_PRIVATE void* subclassData() const;
+ JS_EXPORT_PRIVATE void setSubclassData(void*);
private:
- virtual const ClassInfo* classInfo() const { return &info; }
+ static size_t storageSize(unsigned vectorLength);
+ bool isLengthWritable()
+ {
+ SparseArrayValueMap* map = m_sparseValueMap;
+ return !map || !map->lengthIsReadOnly();
+ }
+
+ void setLengthWritable(ExecState*, bool writable);
+ void putDescriptor(ExecState*, SparseArrayEntry*, PropertyDescriptor&, PropertyDescriptor& old);
+ bool defineOwnNumericProperty(ExecState*, unsigned, PropertyDescriptor&, bool throwException);
+ void allocateSparseMap(JSGlobalData&);
+ void deallocateSparseMap();
bool getOwnPropertySlotSlowCase(ExecState*, unsigned propertyName, PropertySlot&);
- void putSlowCase(ExecState*, unsigned propertyName, JSValue);
+ void putByIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
+ JS_EXPORT_PRIVATE bool putDirectIndexBeyondVectorLength(ExecState*, unsigned propertyName, JSValue, bool shouldThrow);
- bool increaseVectorLength(unsigned newLength);
+ unsigned getNewVectorLength(unsigned desiredLength);
+ bool increaseVectorLength(JSGlobalData&, unsigned newLength);
+ bool unshiftCountSlowCase(JSGlobalData&, unsigned count);
unsigned compactForSorting();
enum ConsistencyCheckType { NormalConsistencyCheck, DestructorConsistencyCheck, SortConsistencyCheck };
void checkConsistency(ConsistencyCheckType = NormalConsistencyCheck);
- unsigned m_vectorLength;
- ArrayStorage* m_storage;
- };
+ unsigned m_vectorLength; // The valid length of m_vector
+ unsigned m_indexBias; // The number of JSValue sized blocks before ArrayStorage.
+ ArrayStorage *m_storage;
- JSArray* asArray(JSValue);
+ // FIXME: Maybe SparseArrayValueMap should be put into its own JSCell?
+ SparseArrayValueMap* m_sparseValueMap;
- inline JSArray* asArray(JSCell* cell)
+ static ptrdiff_t sparseValueMapOffset() { return OBJECT_OFFSETOF(JSArray, m_sparseValueMap); }
+ static ptrdiff_t indexBiasOffset() { return OBJECT_OFFSETOF(JSArray, m_indexBias); }
+ };
+
+ inline JSArray* JSArray::create(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
{
- ASSERT(cell->inherits(&JSArray::info));
- return static_cast<JSArray*>(cell);
+ JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
+ array->finishCreation(globalData, initialLength);
+ return array;
}
- inline JSArray* asArray(JSValue value)
+ inline JSArray* JSArray::tryCreateUninitialized(JSGlobalData& globalData, Structure* structure, unsigned initialLength)
{
- return asArray(value.asCell());
+ JSArray* array = new (NotNull, allocateCell<JSArray>(globalData.heap)) JSArray(globalData, structure);
+ return array->tryFinishCreationUninitialized(globalData, initialLength);
}
- inline bool isJSArray(JSGlobalData* globalData, JSValue v)
+ JSArray* asArray(JSValue);
+
+ inline JSArray* asArray(JSCell* cell)
{
- return v.isCell() && v.asCell()->vptr() == globalData->jsArrayVPtr;
+ ASSERT(cell->inherits(&JSArray::s_info));
+ return jsCast<JSArray*>(cell);
}
- inline bool isJSArray(JSGlobalData* globalData, JSCell* cell) { return cell->vptr() == globalData->jsArrayVPtr; }
- inline void JSArray::markChildrenDirect(MarkStack& markStack)
+ inline JSArray* asArray(JSValue value)
{
- JSObject::markChildrenDirect(markStack);
-
- ArrayStorage* storage = m_storage;
-
- unsigned usedVectorLength = std::min(storage->m_length, m_vectorLength);
- markStack.appendValues(storage->m_vector, usedVectorLength, MayContainNullValues);
-
- if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
- SparseArrayValueMap::iterator end = map->end();
- for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
- markStack.append(it->second);
- }
+ return asArray(value.asCell());
}
- inline void MarkStack::markChildren(JSCell* cell)
+ inline bool isJSArray(JSCell* cell) { return cell->classInfo() == &JSArray::s_info; }
+ inline bool isJSArray(JSValue v) { return v.isCell() && isJSArray(v.asCell()); }
+
+ // Rule from ECMA 15.2 about what an array index is.
+ // Must exactly match string form of an unsigned integer, and be less than 2^32 - 1.
+ inline unsigned Identifier::toArrayIndex(bool& ok) const
{
- ASSERT(Heap::isCellMarked(cell));
- if (!cell->structure()->typeInfo().overridesMarkChildren()) {
-#ifdef NDEBUG
- asObject(cell)->markChildrenDirect(*this);
-#else
- ASSERT(!m_isCheckingForDefaultMarkViolation);
- m_isCheckingForDefaultMarkViolation = true;
- cell->markChildren(*this);
- ASSERT(m_isCheckingForDefaultMarkViolation);
- m_isCheckingForDefaultMarkViolation = false;
-#endif
- return;
- }
- if (cell->vptr() == m_jsArrayVPtr) {
- asArray(cell)->markChildrenDirect(*this);
- return;
- }
- cell->markChildren(*this);
+ unsigned i = toUInt32(ok);
+ if (ok && i >= 0xFFFFFFFFU)
+ ok = false;
+ return i;
}
- inline void MarkStack::drain()
+// The definition of MAX_STORAGE_VECTOR_LENGTH is dependant on the definition storageSize
+// function below - the MAX_STORAGE_VECTOR_LENGTH limit is defined such that the storage
+// size calculation cannot overflow. (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) +
+// (vectorLength * sizeof(WriteBarrier<Unknown>)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
+#define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>))
+
+// These values have to be macros to be used in max() and min() without introducing
+// a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
+#define MIN_SPARSE_ARRAY_INDEX 10000U
+#define MAX_STORAGE_VECTOR_INDEX (MAX_STORAGE_VECTOR_LENGTH - 1)
+ inline size_t JSArray::storageSize(unsigned vectorLength)
{
- while (!m_markSets.isEmpty() || !m_values.isEmpty()) {
- while (!m_markSets.isEmpty() && m_values.size() < 50) {
- ASSERT(!m_markSets.isEmpty());
- MarkSet& current = m_markSets.last();
- ASSERT(current.m_values);
- JSValue* end = current.m_end;
- ASSERT(current.m_values);
- ASSERT(current.m_values != end);
- findNextUnmarkedNullValue:
- ASSERT(current.m_values != end);
- JSValue value = *current.m_values;
- current.m_values++;
-
- JSCell* cell;
- if (!value || !value.isCell() || Heap::isCellMarked(cell = value.asCell())) {
- if (current.m_values == end) {
- m_markSets.removeLast();
- continue;
- }
- goto findNextUnmarkedNullValue;
- }
-
- Heap::markCell(cell);
- if (cell->structure()->typeInfo().type() < CompoundType) {
- if (current.m_values == end) {
- m_markSets.removeLast();
- continue;
- }
- goto findNextUnmarkedNullValue;
- }
-
- if (current.m_values == end)
- m_markSets.removeLast();
-
- markChildren(cell);
- }
- while (!m_values.isEmpty())
- markChildren(m_values.removeLast());
- }
+ ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH);
+
+ // MAX_STORAGE_VECTOR_LENGTH is defined such that provided (vectorLength <= MAX_STORAGE_VECTOR_LENGTH)
+ // - as asserted above - the following calculation cannot overflow.
+ size_t size = (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>)) + (vectorLength * sizeof(WriteBarrier<Unknown>));
+ // Assertion to detect integer overflow in previous calculation (should not be possible, provided that
+ // MAX_STORAGE_VECTOR_LENGTH is correctly defined).
+ ASSERT(((size - (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))) / sizeof(WriteBarrier<Unknown>) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(WriteBarrier<Unknown>))));
+
+ return size;
}
-} // namespace JSC
+ } // namespace JSC
#endif // JSArray_h
projects / apple / javascriptcore.git / blobdiff