]> git.saurik.com Git - apple/javascriptcore.git/blobdiff - runtime/JSArray.cpp
projects / apple / javascriptcore.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
JavaScriptCore-903.tar.gz
[apple/javascriptcore.git] / runtime / JSArray.cpp
diff --git a/runtime/JSArray.cpp b/runtime/JSArray.cpp
index 708ef99a27e3e878b780bda0eeedae2a67413fc0..6bc316363ad3ee98dd6c969a4be1a7c32115579b 100644 (file)
--- a/runtime/JSArray.cpp
+++ b/runtime/JSArray.cpp
@@ -1,6 +1,6 @@
 /*
  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
 /*
  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
- *  Copyright (C) 2003, 2007, 2008 Apple Inc. All rights reserved.
+ *  Copyright (C) 2003, 2007, 2008, 2009 Apple Inc. All rights reserved.
  *  Copyright (C) 2003 Peter Kelly (pmk@post.com)
  *  Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
  *
  *  Copyright (C) 2003 Peter Kelly (pmk@post.com)
  *  Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
  *
@@ -25,14 +25,14 @@
 
 #include "ArrayPrototype.h"
 #include "CachedCall.h"
 
 #include "ArrayPrototype.h"
 #include "CachedCall.h"
+#include "Error.h"
+#include "Executable.h"
 #include "PropertyNameArray.h"
 #include <wtf/AVLTree.h>
 #include <wtf/Assertions.h>
 #include <wtf/OwnPtr.h>
 #include <Operations.h>
 
 #include "PropertyNameArray.h"
 #include <wtf/AVLTree.h>
 #include <wtf/Assertions.h>
 #include <wtf/OwnPtr.h>
 #include <Operations.h>
 
-#define CHECK_ARRAY_CONSISTENCY 0
-
 using namespace std;
 using namespace WTF;
 
 using namespace std;
 using namespace WTF;
 
@@ -78,13 +78,26 @@ ASSERT_CLASS_FITS_IN_CELL(JSArray);
 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
 #define MAX_ARRAY_INDEX 0xFFFFFFFEU
 
 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
 #define MAX_ARRAY_INDEX 0xFFFFFFFEU
 
+// The value BASE_VECTOR_LEN is the maximum number of vector elements we'll allocate
+// for an array that was created with a sepcified length (e.g. a = new Array(123))
+#define BASE_VECTOR_LEN 4U
+    
+// The upper bound to the size we'll grow a zero length array when the first element
+// is added.
+#define FIRST_VECTOR_GROW 4U
+
 // Our policy for when to use a vector and when to use a sparse map.
 // For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
 // When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
 // as long as it is 1/8 full. If more sparse than that, we use a map.
 static const unsigned minDensityMultiplier = 8;
 
 // Our policy for when to use a vector and when to use a sparse map.
 // For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
 // When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
 // as long as it is 1/8 full. If more sparse than that, we use a map.
 static const unsigned minDensityMultiplier = 8;
 
-const ClassInfo JSArray::info = {"Array", 0, 0, 0};
+const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0};
+
+// We keep track of the size of the last array after it was grown.  We use this
+// as a simple heuristic for as the value to grow the next array from size 0.
+// This value is capped by the constant FIRST_VECTOR_GROW defined above.
+static unsigned lastArraySize = 0;
 
 static inline size_t storageSize(unsigned vectorLength)
 {
 
 static inline size_t storageSize(unsigned vectorLength)
 {
@@ -100,21 +113,6 @@ static inline size_t storageSize(unsigned vectorLength)
     return size;
 }
 
     return size;
 }
 
-static inline unsigned increasedVectorLength(unsigned newLength)
-{
-    ASSERT(newLength <= MAX_STORAGE_VECTOR_LENGTH);
-
-    // Mathematically equivalent to:
-    //   increasedLength = (newLength * 3 + 1) / 2;
-    // or:
-    //   increasedLength = (unsigned)ceil(newLength * 1.5));
-    // This form is not prone to internal overflow.
-    unsigned increasedLength = newLength + (newLength >> 1) + (newLength & 1);
-    ASSERT(increasedLength >= newLength);
-
-    return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
-}
-
 static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
 {
     return length / minDensityMultiplier <= numValues;
 static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
 {
     return length / minDensityMultiplier <= numValues;
@@ -128,122 +126,202 @@ inline void JSArray::checkConsistency(ConsistencyCheckType)
 
 #endif
 
 
 #endif
 
-JSArray::JSArray(PassRefPtr<Structure> structure)
-    : JSObject(structure)
+JSArray::JSArray(VPtrStealingHackType)
+    : JSNonFinalObject(VPtrStealingHack)
 {
 {
+}
+
+JSArray::JSArray(JSGlobalData& globalData, Structure* structure)
+    : JSNonFinalObject(globalData, structure)
+{
+    ASSERT(inherits(&s_info));
+
     unsigned initialCapacity = 0;
 
     m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
     unsigned initialCapacity = 0;
 
     m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
-    m_storage->m_vectorLength = initialCapacity;
-
-    m_fastAccessCutoff = 0;
+    m_storage->m_allocBase = m_storage;
+    m_indexBias = 0;
+    m_vectorLength = initialCapacity;
 
     checkConsistency();
 
     checkConsistency();
+
+    Heap::heap(this)->reportExtraMemoryCost(storageSize(0));
 }
 
 }
 
-JSArray::JSArray(PassRefPtr<Structure> structure, unsigned initialLength)
-    : JSObject(structure)
+JSArray::JSArray(JSGlobalData& globalData, Structure* structure, unsigned initialLength, ArrayCreationMode creationMode)
+    : JSNonFinalObject(globalData, structure)
 {
 {
-    unsigned initialCapacity = min(initialLength, MIN_SPARSE_ARRAY_INDEX);
-
+    ASSERT(inherits(&s_info));
+
+    unsigned initialCapacity;
+    if (creationMode == CreateCompact)
+        initialCapacity = initialLength;
+    else
+        initialCapacity = min(BASE_VECTOR_LEN, MIN_SPARSE_ARRAY_INDEX);
+    
     m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
     m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
+    m_storage->m_allocBase = m_storage;
     m_storage->m_length = initialLength;
     m_storage->m_length = initialLength;
-    m_storage->m_vectorLength = initialCapacity;
-    m_storage->m_numValuesInVector = 0;
+    m_indexBias = 0;
+    m_vectorLength = initialCapacity;
     m_storage->m_sparseValueMap = 0;
     m_storage->m_sparseValueMap = 0;
-    m_storage->lazyCreationData = 0;
+    m_storage->subclassData = 0;
+    m_storage->reportedMapCapacity = 0;
 
 
-    JSValue* vector = m_storage->m_vector;
-    for (size_t i = 0; i < initialCapacity; ++i)
-        vector[i] = JSValue();
-
-    m_fastAccessCutoff = 0;
+    if (creationMode == CreateCompact) {
+#if CHECK_ARRAY_CONSISTENCY
+        m_storage->m_inCompactInitialization = !!initialCapacity;
+#endif
+        m_storage->m_length = 0;
+        m_storage->m_numValuesInVector = initialCapacity;
+    } else {
+#if CHECK_ARRAY_CONSISTENCY
+        storage->m_inCompactInitialization = false;
+#endif
+        m_storage->m_length = initialLength;
+        m_storage->m_numValuesInVector = 0;
+        WriteBarrier<Unknown>* vector = m_storage->m_vector;
+        for (size_t i = 0; i < initialCapacity; ++i)
+            vector[i].clear();
+    }
 
     checkConsistency();
 
     checkConsistency();
-
-    Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValue));
+    
+    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity));
 }
 
 }
 
-JSArray::JSArray(PassRefPtr<Structure> structure, const ArgList& list)
-    : JSObject(structure)
+JSArray::JSArray(JSGlobalData& globalData, Structure* structure, const ArgList& list)
+    : JSNonFinalObject(globalData, structure)
 {
 {
-    unsigned initialCapacity = list.size();
+    ASSERT(inherits(&s_info));
 
 
-    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
+    unsigned initialCapacity = list.size();
+    unsigned initialStorage;
+    
+    // If the ArgList is empty, allocate space for 3 entries.  This value empirically
+    // works well for benchmarks.
+    if (!initialCapacity)
+        initialStorage = 3;
+    else
+        initialStorage = initialCapacity;
+    
+    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialStorage)));
+    m_storage->m_allocBase = m_storage;
+    m_indexBias = 0;
     m_storage->m_length = initialCapacity;
     m_storage->m_length = initialCapacity;
-    m_storage->m_vectorLength = initialCapacity;
+    m_vectorLength = initialStorage;
     m_storage->m_numValuesInVector = initialCapacity;
     m_storage->m_sparseValueMap = 0;
     m_storage->m_numValuesInVector = initialCapacity;
     m_storage->m_sparseValueMap = 0;
+    m_storage->subclassData = 0;
+    m_storage->reportedMapCapacity = 0;
+#if CHECK_ARRAY_CONSISTENCY
+    m_storage->m_inCompactInitialization = false;
+#endif
 
     size_t i = 0;
 
     size_t i = 0;
+    WriteBarrier<Unknown>* vector = m_storage->m_vector;
     ArgList::const_iterator end = list.end();
     for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
     ArgList::const_iterator end = list.end();
     for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
-        m_storage->m_vector[i] = *it;
-
-    m_fastAccessCutoff = initialCapacity;
+        vector[i].set(globalData, this, *it);
+    for (; i < initialStorage; i++)
+        vector[i].clear();
 
     checkConsistency();
 
 
     checkConsistency();
 
-    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity));
+    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialStorage));
 }
 
 JSArray::~JSArray()
 {
 }
 
 JSArray::~JSArray()
 {
+    ASSERT(vptr() == JSGlobalData::jsArrayVPtr);
     checkConsistency(DestructorConsistencyCheck);
 
     delete m_storage->m_sparseValueMap;
     checkConsistency(DestructorConsistencyCheck);
 
     delete m_storage->m_sparseValueMap;
-    fastFree(m_storage);
+    fastFree(m_storage->m_allocBase);
 }
 
 bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
 {
     ArrayStorage* storage = m_storage;
 }
 
 bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
 {
     ArrayStorage* storage = m_storage;
-
+    
     if (i >= storage->m_length) {
         if (i > MAX_ARRAY_INDEX)
             return getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
         return false;
     }
 
     if (i >= storage->m_length) {
         if (i > MAX_ARRAY_INDEX)
             return getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
         return false;
     }
 
-    if (i < storage->m_vectorLength) {
-        JSValue& valueSlot = storage->m_vector[i];
-        if (valueSlot) {
-            slot.setValueSlot(&valueSlot);
+    if (i < m_vectorLength) {
+        JSValue value = storage->m_vector[i].get();
+        if (value) {
+            slot.setValue(value);
             return true;
         }
     } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
         if (i >= MIN_SPARSE_ARRAY_INDEX) {
             SparseArrayValueMap::iterator it = map->find(i);
             if (it != map->end()) {
             return true;
         }
     } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
         if (i >= MIN_SPARSE_ARRAY_INDEX) {
             SparseArrayValueMap::iterator it = map->find(i);
             if (it != map->end()) {
-                slot.setValueSlot(&it->second);
+                slot.setValue(it->second.get());
                 return true;
             }
         }
     }
 
                 return true;
             }
         }
     }
 
-    return false;
+    return JSObject::getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
 }
 
 bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
 {
     if (propertyName == exec->propertyNames().length) {
 }
 
 bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
 {
     if (propertyName == exec->propertyNames().length) {
-        slot.setValue(jsNumber(exec, length()));
+        slot.setValue(jsNumber(length()));
         return true;
     }
 
     bool isArrayIndex;
         return true;
     }
 
     bool isArrayIndex;
-    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
+    unsigned i = propertyName.toArrayIndex(isArrayIndex);
     if (isArrayIndex)
         return JSArray::getOwnPropertySlot(exec, i, slot);
 
     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
 }
 
     if (isArrayIndex)
         return JSArray::getOwnPropertySlot(exec, i, slot);
 
     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
 }
 
+bool JSArray::getOwnPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
+{
+    if (propertyName == exec->propertyNames().length) {
+        descriptor.setDescriptor(jsNumber(length()), DontDelete | DontEnum);
+        return true;
+    }
+
+    ArrayStorage* storage = m_storage;
+    
+    bool isArrayIndex;
+    unsigned i = propertyName.toArrayIndex(isArrayIndex);
+    if (isArrayIndex) {
+        if (i >= storage->m_length)
+            return false;
+        if (i < m_vectorLength) {
+            WriteBarrier<Unknown>& value = storage->m_vector[i];
+            if (value) {
+                descriptor.setDescriptor(value.get(), 0);
+                return true;
+            }
+        } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
+            if (i >= MIN_SPARSE_ARRAY_INDEX) {
+                SparseArrayValueMap::iterator it = map->find(i);
+                if (it != map->end()) {
+                    descriptor.setDescriptor(it->second.get(), 0);
+                    return true;
+                }
+            }
+        }
+    }
+    return JSObject::getOwnPropertyDescriptor(exec, propertyName, descriptor);
+}
+
 // ECMA 15.4.5.1
 void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
 {
     bool isArrayIndex;
 // ECMA 15.4.5.1
 void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
 {
     bool isArrayIndex;
-    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
+    unsigned i = propertyName.toArrayIndex(isArrayIndex);
     if (isArrayIndex) {
         put(exec, i, value);
         return;
     if (isArrayIndex) {
         put(exec, i, value);
         return;
@@ -252,7 +330,7 @@ void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value
     if (propertyName == exec->propertyNames().length) {
         unsigned newLength = value.toUInt32(exec);
         if (value.toNumber(exec) != static_cast<double>(newLength)) {
     if (propertyName == exec->propertyNames().length) {
         unsigned newLength = value.toUInt32(exec);
         if (value.toNumber(exec) != static_cast<double>(newLength)) {
-            throwError(exec, RangeError, "Invalid array length.");
+            throwError(exec, createRangeError(exec, "Invalid array length."));
             return;
         }
         setLength(newLength);
             return;
         }
         setLength(newLength);
@@ -266,22 +344,23 @@ void JSArray::put(ExecState* exec, unsigned i, JSValue value)
 {
     checkConsistency();
 
 {
     checkConsistency();
 
-    unsigned length = m_storage->m_length;
+    ArrayStorage* storage = m_storage;
+
+    unsigned length = storage->m_length;
     if (i >= length && i <= MAX_ARRAY_INDEX) {
         length = i + 1;
     if (i >= length && i <= MAX_ARRAY_INDEX) {
         length = i + 1;
-        m_storage->m_length = length;
+        storage->m_length = length;
     }
 
     }
 
-    if (i < m_storage->m_vectorLength) {
-        JSValue& valueSlot = m_storage->m_vector[i];
+    if (i < m_vectorLength) {
+        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
         if (valueSlot) {
         if (valueSlot) {
-            valueSlot = value;
+            valueSlot.set(exec->globalData(), this, value);
             checkConsistency();
             return;
         }
             checkConsistency();
             return;
         }
-        valueSlot = value;
-        if (++m_storage->m_numValuesInVector == m_storage->m_length)
-            m_fastAccessCutoff = m_storage->m_length;
+        valueSlot.set(exec->globalData(), this, value);
+        ++storage->m_numValuesInVector;
         checkConsistency();
         return;
     }
         checkConsistency();
         return;
     }
@@ -292,6 +371,7 @@ void JSArray::put(ExecState* exec, unsigned i, JSValue value)
 NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
 {
     ArrayStorage* storage = m_storage;
 NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
 {
     ArrayStorage* storage = m_storage;
+    
     SparseArrayValueMap* map = storage->m_sparseValueMap;
 
     if (i >= MIN_SPARSE_ARRAY_INDEX) {
     SparseArrayValueMap* map = storage->m_sparseValueMap;
 
     if (i >= MIN_SPARSE_ARRAY_INDEX) {
@@ -302,13 +382,24 @@ NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue valu
         }
 
         // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
         }
 
         // We miss some cases where we could compact the storage, such as a large array that is being filled from the end
-        // (which will only be compacted as we reach indices that are less than cutoff) - but this makes the check much faster.
+        // (which will only be compacted as we reach indices that are less than MIN_SPARSE_ARRAY_INDEX) - but this makes the check much faster.
         if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
             if (!map) {
                 map = new SparseArrayValueMap;
                 storage->m_sparseValueMap = map;
             }
         if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
             if (!map) {
                 map = new SparseArrayValueMap;
                 storage->m_sparseValueMap = map;
             }
-            map->set(i, value);
+
+            WriteBarrier<Unknown> temp;
+            pair<SparseArrayValueMap::iterator, bool> result = map->add(i, temp);
+            result.first->second.set(exec->globalData(), this, value);
+            if (!result.second) // pre-existing entry
+                return;
+
+            size_t capacity = map->capacity();
+            if (capacity != storage->reportedMapCapacity) {
+                Heap::heap(this)->reportExtraMemoryCost((capacity - storage->reportedMapCapacity) * (sizeof(unsigned) + sizeof(JSValue)));
+                storage->reportedMapCapacity = capacity;
+            }
             return;
         }
     }
             return;
         }
     }
@@ -318,9 +409,8 @@ NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue valu
     if (!map || map->isEmpty()) {
         if (increaseVectorLength(i + 1)) {
             storage = m_storage;
     if (!map || map->isEmpty()) {
         if (increaseVectorLength(i + 1)) {
             storage = m_storage;
-            storage->m_vector[i] = value;
-            if (++storage->m_numValuesInVector == storage->m_length)
-                m_fastAccessCutoff = storage->m_length;
+            storage->m_vector[i].set(exec->globalData(), this, value);
+            ++storage->m_numValuesInVector;
             checkConsistency();
         } else
             throwOutOfMemoryError(exec);
             checkConsistency();
         } else
             throwOutOfMemoryError(exec);
@@ -329,16 +419,17 @@ NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue valu
 
     // Decide how many values it would be best to move from the map.
     unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
 
     // Decide how many values it would be best to move from the map.
     unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
-    unsigned newVectorLength = increasedVectorLength(i + 1);
-    for (unsigned j = max(storage->m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
+    unsigned newVectorLength = getNewVectorLength(i + 1);
+    for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
         newNumValuesInVector += map->contains(j);
     if (i >= MIN_SPARSE_ARRAY_INDEX)
         newNumValuesInVector -= map->contains(i);
     if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
         newNumValuesInVector += map->contains(j);
     if (i >= MIN_SPARSE_ARRAY_INDEX)
         newNumValuesInVector -= map->contains(i);
     if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
+        unsigned needLength = max(i + 1, storage->m_length);
         unsigned proposedNewNumValuesInVector = newNumValuesInVector;
         // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
         unsigned proposedNewNumValuesInVector = newNumValuesInVector;
         // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
-        while (newVectorLength < MAX_STORAGE_VECTOR_LENGTH) {
-            unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
+        while ((newVectorLength < needLength) && (newVectorLength < MAX_STORAGE_VECTOR_LENGTH)) {
+            unsigned proposedNewVectorLength = getNewVectorLength(newVectorLength + 1);
             for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
                 proposedNewNumValuesInVector += map->contains(j);
             if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
             for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
                 proposedNewNumValuesInVector += map->contains(j);
             if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
@@ -348,42 +439,49 @@ NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue valu
         }
     }
 
         }
     }
 
-    storage = static_cast<ArrayStorage*>(tryFastRealloc(storage, storageSize(newVectorLength)));
-    if (!storage) {
+    void* baseStorage = storage->m_allocBase;
+    
+    if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) {
         throwOutOfMemoryError(exec);
         return;
     }
 
         throwOutOfMemoryError(exec);
         return;
     }
 
-    unsigned vectorLength = storage->m_vectorLength;
-
-    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
+    m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
+    m_storage->m_allocBase = baseStorage;
+    storage = m_storage;
+    
+    unsigned vectorLength = m_vectorLength;
+    WriteBarrier<Unknown>* vector = storage->m_vector;
 
     if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
         for (unsigned j = vectorLength; j < newVectorLength; ++j)
 
     if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
         for (unsigned j = vectorLength; j < newVectorLength; ++j)
-            storage->m_vector[j] = JSValue();
+            vector[j].clear();
         if (i > MIN_SPARSE_ARRAY_INDEX)
             map->remove(i);
     } else {
         for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
         if (i > MIN_SPARSE_ARRAY_INDEX)
             map->remove(i);
     } else {
         for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
-            storage->m_vector[j] = JSValue();
+            vector[j].clear();
+        JSGlobalData& globalData = exec->globalData();
         for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
         for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
-            storage->m_vector[j] = map->take(j);
+            vector[j].set(globalData, this, map->take(j).get());
     }
 
     }
 
-    storage->m_vector[i] = value;
+    ASSERT(i < newVectorLength);
 
 
-    storage->m_vectorLength = newVectorLength;
+    m_vectorLength = newVectorLength;
     storage->m_numValuesInVector = newNumValuesInVector;
 
     storage->m_numValuesInVector = newNumValuesInVector;
 
-    m_storage = storage;
+    storage->m_vector[i].set(exec->globalData(), this, value);
 
     checkConsistency();
 
     checkConsistency();
+
+    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
 }
 
 bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName)
 {
     bool isArrayIndex;
 }
 
 bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName)
 {
     bool isArrayIndex;
-    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
+    unsigned i = propertyName.toArrayIndex(isArrayIndex);
     if (isArrayIndex)
         return deleteProperty(exec, i);
 
     if (isArrayIndex)
         return deleteProperty(exec, i);
 
@@ -398,17 +496,15 @@ bool JSArray::deleteProperty(ExecState* exec, unsigned i)
     checkConsistency();
 
     ArrayStorage* storage = m_storage;
     checkConsistency();
 
     ArrayStorage* storage = m_storage;
-
-    if (i < storage->m_vectorLength) {
-        JSValue& valueSlot = storage->m_vector[i];
+    
+    if (i < m_vectorLength) {
+        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
         if (!valueSlot) {
             checkConsistency();
             return false;
         }
         if (!valueSlot) {
             checkConsistency();
             return false;
         }
-        valueSlot = JSValue();
+        valueSlot.clear();
         --storage->m_numValuesInVector;
         --storage->m_numValuesInVector;
-        if (m_fastAccessCutoff > i)
-            m_fastAccessCutoff = i;
         checkConsistency();
         return true;
     }
         checkConsistency();
         return true;
     }
@@ -432,15 +528,15 @@ bool JSArray::deleteProperty(ExecState* exec, unsigned i)
     return false;
 }
 
     return false;
 }
 
-void JSArray::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
+void JSArray::getOwnPropertyNames(ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
 {
     // FIXME: Filling PropertyNameArray with an identifier for every integer
     // is incredibly inefficient for large arrays. We need a different approach,
     // which almost certainly means a different structure for PropertyNameArray.
 
     ArrayStorage* storage = m_storage;
 {
     // FIXME: Filling PropertyNameArray with an identifier for every integer
     // is incredibly inefficient for large arrays. We need a different approach,
     // which almost certainly means a different structure for PropertyNameArray.
 
     ArrayStorage* storage = m_storage;
-
-    unsigned usedVectorLength = min(storage->m_length, storage->m_vectorLength);
+    
+    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
     for (unsigned i = 0; i < usedVectorLength; ++i) {
         if (storage->m_vector[i])
             propertyNames.add(Identifier::from(exec, i));
     for (unsigned i = 0; i < usedVectorLength; ++i) {
         if (storage->m_vector[i])
             propertyNames.add(Identifier::from(exec, i));
@@ -452,7 +548,37 @@ void JSArray::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames
             propertyNames.add(Identifier::from(exec, it->first));
     }
 
             propertyNames.add(Identifier::from(exec, it->first));
     }
 
-    JSObject::getPropertyNames(exec, propertyNames);
+    if (mode == IncludeDontEnumProperties)
+        propertyNames.add(exec->propertyNames().length);
+
+    JSObject::getOwnPropertyNames(exec, propertyNames, mode);
+}
+
+ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
+{
+    ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);
+
+    unsigned increasedLength;
+    unsigned maxInitLength = min(m_storage->m_length, 100000U);
+
+    if (desiredLength < maxInitLength)
+        increasedLength = maxInitLength;
+    else if (!m_vectorLength)
+        increasedLength = max(desiredLength, lastArraySize);
+    else {
+        // Mathematically equivalent to:
+        //   increasedLength = (newLength * 3 + 1) / 2;
+        // or:
+        //   increasedLength = (unsigned)ceil(newLength * 1.5));
+        // This form is not prone to internal overflow.
+        increasedLength = desiredLength + (desiredLength >> 1) + (desiredLength & 1);
+    }
+
+    ASSERT(increasedLength >= desiredLength);
+
+    lastArraySize = min(increasedLength, FIRST_VECTOR_GROW);
+
+    return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
 }
 
 bool JSArray::increaseVectorLength(unsigned newLength)
 }
 
 bool JSArray::increaseVectorLength(unsigned newLength)
@@ -462,42 +588,85 @@ bool JSArray::increaseVectorLength(unsigned newLength)
 
     ArrayStorage* storage = m_storage;
 
 
     ArrayStorage* storage = m_storage;
 
-    unsigned vectorLength = storage->m_vectorLength;
+    unsigned vectorLength = m_vectorLength;
     ASSERT(newLength > vectorLength);
     ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
     ASSERT(newLength > vectorLength);
     ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
-    unsigned newVectorLength = increasedVectorLength(newLength);
+    unsigned newVectorLength = getNewVectorLength(newLength);
+    void* baseStorage = storage->m_allocBase;
 
 
-    storage = static_cast<ArrayStorage*>(tryFastRealloc(storage, storageSize(newVectorLength)));
-    if (!storage)
+    if (!tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage))
         return false;
 
         return false;
 
-    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
-    storage->m_vectorLength = newVectorLength;
+    storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
+    m_storage->m_allocBase = baseStorage;
 
 
+    WriteBarrier<Unknown>* vector = storage->m_vector;
     for (unsigned i = vectorLength; i < newVectorLength; ++i)
     for (unsigned i = vectorLength; i < newVectorLength; ++i)
-        storage->m_vector[i] = JSValue();
+        vector[i].clear();
+
+    m_vectorLength = newVectorLength;
+    
+    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
 
 
-    m_storage = storage;
     return true;
 }
 
     return true;
 }
 
-void JSArray::setLength(unsigned newLength)
+bool JSArray::increaseVectorPrefixLength(unsigned newLength)
 {
 {
-    checkConsistency();
+    // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
+    // to the vector. Callers have to account for that, because they can do it more efficiently.
+    
+    ArrayStorage* storage = m_storage;
+    
+    unsigned vectorLength = m_vectorLength;
+    ASSERT(newLength > vectorLength);
+    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
+    unsigned newVectorLength = getNewVectorLength(newLength);
 
 
+    void* newBaseStorage = fastMalloc(storageSize(newVectorLength + m_indexBias));
+    if (!newBaseStorage)
+        return false;
+    
+    m_indexBias += newVectorLength - newLength;
+    
+    m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(newBaseStorage) + m_indexBias * sizeof(JSValue));
+
+    memcpy(m_storage, storage, storageSize(0));
+    memcpy(&m_storage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], vectorLength * sizeof(JSValue));
+    
+    m_storage->m_allocBase = newBaseStorage;
+    m_vectorLength = newLength;
+    
+    fastFree(storage->m_allocBase);
+    ASSERT(newLength > vectorLength);
+    unsigned delta = newLength - vectorLength;
+    for (unsigned i = 0; i < delta; i++)
+        m_storage->m_vector[i].clear();
+    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
+    
+    return true;
+}
+    
+
+void JSArray::setLength(unsigned newLength)
+{
     ArrayStorage* storage = m_storage;
     ArrayStorage* storage = m_storage;
+    
+#if CHECK_ARRAY_CONSISTENCY
+    if (!storage->m_inCompactInitialization)
+        checkConsistency();
+    else
+        storage->m_inCompactInitialization = false;
+#endif
 
 
-    unsigned length = m_storage->m_length;
+    unsigned length = storage->m_length;
 
     if (newLength < length) {
 
     if (newLength < length) {
-        if (m_fastAccessCutoff > newLength)
-            m_fastAccessCutoff = newLength;
-
-        unsigned usedVectorLength = min(length, storage->m_vectorLength);
+        unsigned usedVectorLength = min(length, m_vectorLength);
         for (unsigned i = newLength; i < usedVectorLength; ++i) {
         for (unsigned i = newLength; i < usedVectorLength; ++i) {
-            JSValue& valueSlot = storage->m_vector[i];
+            WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
             bool hadValue = valueSlot;
             bool hadValue = valueSlot;
-            valueSlot = JSValue();
+            valueSlot.clear();
             storage->m_numValuesInVector -= hadValue;
         }
 
             storage->m_numValuesInVector -= hadValue;
         }
 
@@ -515,7 +684,7 @@ void JSArray::setLength(unsigned newLength)
         }
     }
 
         }
     }
 
-    m_storage->m_length = newLength;
+    storage->m_length = newLength;
 
     checkConsistency();
 }
 
     checkConsistency();
 }
@@ -524,7 +693,9 @@ JSValue JSArray::pop()
 {
     checkConsistency();
 
 {
     checkConsistency();
 
-    unsigned length = m_storage->m_length;
+    ArrayStorage* storage = m_storage;
+    
+    unsigned length = storage->m_length;
     if (!length)
         return jsUndefined();
 
     if (!length)
         return jsUndefined();
 
@@ -532,37 +703,30 @@ JSValue JSArray::pop()
 
     JSValue result;
 
 
     JSValue result;
 
-    if (m_fastAccessCutoff > length) {
-        JSValue& valueSlot = m_storage->m_vector[length];
-        result = valueSlot;
-        ASSERT(result);
-        valueSlot = JSValue();
-        --m_storage->m_numValuesInVector;
-        m_fastAccessCutoff = length;
-    } else if (length < m_storage->m_vectorLength) {
-        JSValue& valueSlot = m_storage->m_vector[length];
-        result = valueSlot;
-        valueSlot = JSValue();
-        if (result)
-            --m_storage->m_numValuesInVector;
-        else
+    if (length < m_vectorLength) {
+        WriteBarrier<Unknown>& valueSlot = storage->m_vector[length];
+        if (valueSlot) {
+            --storage->m_numValuesInVector;
+            result = valueSlot.get();
+            valueSlot.clear();
+        } else
             result = jsUndefined();
     } else {
         result = jsUndefined();
             result = jsUndefined();
     } else {
         result = jsUndefined();
-        if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
+        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
             SparseArrayValueMap::iterator it = map->find(length);
             if (it != map->end()) {
             SparseArrayValueMap::iterator it = map->find(length);
             if (it != map->end()) {
-                result = it->second;
+                result = it->second.get();
                 map->remove(it);
                 if (map->isEmpty()) {
                     delete map;
                 map->remove(it);
                 if (map->isEmpty()) {
                     delete map;
-                    m_storage->m_sparseValueMap = 0;
+                    storage->m_sparseValueMap = 0;
                 }
             }
         }
     }
 
                 }
             }
         }
     }
 
-    m_storage->m_length = length;
+    storage->m_length = length;
 
     checkConsistency();
 
 
     checkConsistency();
 
@@ -572,23 +736,25 @@ JSValue JSArray::pop()
 void JSArray::push(ExecState* exec, JSValue value)
 {
     checkConsistency();
 void JSArray::push(ExecState* exec, JSValue value)
 {
     checkConsistency();
+    
+    ArrayStorage* storage = m_storage;
 
 
-    if (m_storage->m_length < m_storage->m_vectorLength) {
-        ASSERT(!m_storage->m_vector[m_storage->m_length]);
-        m_storage->m_vector[m_storage->m_length] = value;
-        if (++m_storage->m_numValuesInVector == ++m_storage->m_length)
-            m_fastAccessCutoff = m_storage->m_length;
+    if (storage->m_length < m_vectorLength) {
+        storage->m_vector[storage->m_length].set(exec->globalData(), this, value);
+        ++storage->m_numValuesInVector;
+        ++storage->m_length;
         checkConsistency();
         return;
     }
 
         checkConsistency();
         return;
     }
 
-    if (m_storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
-        SparseArrayValueMap* map = m_storage->m_sparseValueMap;
+    if (storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
+        SparseArrayValueMap* map = storage->m_sparseValueMap;
         if (!map || map->isEmpty()) {
         if (!map || map->isEmpty()) {
-            if (increaseVectorLength(m_storage->m_length + 1)) {
-                m_storage->m_vector[m_storage->m_length] = value;
-                if (++m_storage->m_numValuesInVector == ++m_storage->m_length)
-                    m_fastAccessCutoff = m_storage->m_length;
+            if (increaseVectorLength(storage->m_length + 1)) {
+                storage = m_storage;
+                storage->m_vector[storage->m_length].set(exec->globalData(), this, value);
+                ++storage->m_numValuesInVector;
+                ++storage->m_length;
                 checkConsistency();
                 return;
             }
                 checkConsistency();
                 return;
             }
@@ -598,30 +764,108 @@ void JSArray::push(ExecState* exec, JSValue value)
         }
     }
 
         }
     }
 
-    putSlowCase(exec, m_storage->m_length++, value);
+    putSlowCase(exec, storage->m_length++, value);
 }
 
 }
 
-void JSArray::mark()
+void JSArray::shiftCount(ExecState* exec, int count)
 {
 {
-    JSObject::mark();
-
+    ASSERT(count > 0);
+    
     ArrayStorage* storage = m_storage;
     ArrayStorage* storage = m_storage;
+    
+    unsigned oldLength = storage->m_length;
+    
+    if (!oldLength)
+        return;
+    
+    if (oldLength != storage->m_numValuesInVector) {
+        // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
+        // which means we need to go through each entry looking for the the "empty"
+        // slots and then fill them with possible properties.  See ECMA spec.
+        // 15.4.4.9 steps 11 through 13.
+        for (unsigned i = count; i < oldLength; ++i) {
+            if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
+                PropertySlot slot(this);
+                JSValue p = prototype();
+                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
+                    put(exec, i, slot.getValue(exec, i));
+            }
+        }
 
 
-    unsigned usedVectorLength = min(storage->m_length, storage->m_vectorLength);
-    for (unsigned i = 0; i < usedVectorLength; ++i) {
-        JSValue value = storage->m_vector[i];
-        if (value && !value.marked())
-            value.mark();
+        storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
+
+        // Need to decrement numValuesInvector based on number of real entries
+        for (unsigned i = 0; i < (unsigned)count; ++i)
+            if ((i < m_vectorLength) && (storage->m_vector[i]))
+                --storage->m_numValuesInVector;
+    } else
+        storage->m_numValuesInVector -= count;
+    
+    storage->m_length -= count;
+    
+    if (m_vectorLength) {
+        count = min(m_vectorLength, (unsigned)count);
+        
+        m_vectorLength -= count;
+        
+        if (m_vectorLength) {
+            char* newBaseStorage = reinterpret_cast<char*>(storage) + count * sizeof(JSValue);
+            memmove(newBaseStorage, storage, storageSize(0));
+            m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
+
+            m_indexBias += count;
+        }
     }
     }
+}
+    
+void JSArray::unshiftCount(ExecState* exec, int count)
+{
+    ArrayStorage* storage = m_storage;
 
 
-    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
-        SparseArrayValueMap::iterator end = map->end();
-        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
-            JSValue value = it->second;
-            if (!value.marked())
-                value.mark();
+    ASSERT(m_indexBias >= 0);
+    ASSERT(count >= 0);
+    
+    unsigned length = storage->m_length;
+    
+    if (length != storage->m_numValuesInVector) {
+        // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
+        // which means we need to go through each entry looking for the the "empty"
+        // slots and then fill them with possible properties.  See ECMA spec.
+        // 15.4.4.13 steps 8 through 10.
+        for (unsigned i = 0; i < length; ++i) {
+            if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
+                PropertySlot slot(this);
+                JSValue p = prototype();
+                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
+                    put(exec, i, slot.getValue(exec, i));
+            }
         }
     }
         }
     }
+    
+    storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
+    
+    if (m_indexBias >= count) {
+        m_indexBias -= count;
+        char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(JSValue);
+        memmove(newBaseStorage, storage, storageSize(0));
+        m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
+        m_vectorLength += count;
+    } else if (!increaseVectorPrefixLength(m_vectorLength + count)) {
+        throwOutOfMemoryError(exec);
+        return;
+    }
+
+    WriteBarrier<Unknown>* vector = m_storage->m_vector;
+    for (int i = 0; i < count; i++)
+        vector[i].clear();
+}
+
+void JSArray::visitChildren(SlotVisitor& visitor)
+{
+    ASSERT_GC_OBJECT_INHERITS(this, &s_info);
+    COMPILE_ASSERT(StructureFlags & OverridesVisitChildren, OverridesVisitChildrenWithoutSettingFlag);
+    ASSERT(structure()->typeInfo().overridesVisitChildren());
+    visitChildrenDirect(visitor);
 }
 
 static int compareNumbersForQSort(const void* a, const void* b)
 }
 
 static int compareNumbersForQSort(const void* a, const void* b)
@@ -631,19 +875,19 @@ static int compareNumbersForQSort(const void* a, const void* b)
     return (da > db) - (da < db);
 }
 
     return (da > db) - (da < db);
 }
 
-typedef std::pair<JSValue, UString> ValueStringPair;
-
 static int compareByStringPairForQSort(const void* a, const void* b)
 {
     const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
     const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
 static int compareByStringPairForQSort(const void* a, const void* b)
 {
     const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
     const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
-    return compare(va->second, vb->second);
+    return codePointCompare(va->second, vb->second);
 }
 
 void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
 {
 }
 
 void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
 {
+    ArrayStorage* storage = m_storage;
+
     unsigned lengthNotIncludingUndefined = compactForSorting();
     unsigned lengthNotIncludingUndefined = compactForSorting();
-    if (m_storage->m_sparseValueMap) {
+    if (storage->m_sparseValueMap) {
         throwOutOfMemoryError(exec);
         return;
     }
         throwOutOfMemoryError(exec);
         return;
     }
@@ -652,9 +896,9 @@ void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType cal
         return;
         
     bool allValuesAreNumbers = true;
         return;
         
     bool allValuesAreNumbers = true;
-    size_t size = m_storage->m_numValuesInVector;
+    size_t size = storage->m_numValuesInVector;
     for (size_t i = 0; i < size; ++i) {
     for (size_t i = 0; i < size; ++i) {
-        if (!m_storage->m_vector[i].isNumber()) {
+        if (!storage->m_vector[i].isNumber()) {
             allValuesAreNumbers = false;
             break;
         }
             allValuesAreNumbers = false;
             break;
         }
@@ -666,15 +910,17 @@ void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType cal
     // For numeric comparison, which is fast, qsort is faster than mergesort. We
     // also don't require mergesort's stability, since there's no user visible
     // side-effect from swapping the order of equal primitive values.
     // For numeric comparison, which is fast, qsort is faster than mergesort. We
     // also don't require mergesort's stability, since there's no user visible
     // side-effect from swapping the order of equal primitive values.
-    qsort(m_storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort);
+    qsort(storage->m_vector, size, sizeof(JSValue), compareNumbersForQSort);
 
     checkConsistency(SortConsistencyCheck);
 }
 
 void JSArray::sort(ExecState* exec)
 {
 
     checkConsistency(SortConsistencyCheck);
 }
 
 void JSArray::sort(ExecState* exec)
 {
+    ArrayStorage* storage = m_storage;
+
     unsigned lengthNotIncludingUndefined = compactForSorting();
     unsigned lengthNotIncludingUndefined = compactForSorting();
-    if (m_storage->m_sparseValueMap) {
+    if (storage->m_sparseValueMap) {
         throwOutOfMemoryError(exec);
         return;
     }
         throwOutOfMemoryError(exec);
         return;
     }
@@ -692,24 +938,25 @@ void JSArray::sort(ExecState* exec)
         throwOutOfMemoryError(exec);
         return;
     }
         throwOutOfMemoryError(exec);
         return;
     }
+    
+    Heap::heap(this)->pushTempSortVector(&values);
 
     for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
 
     for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
-        JSValue value = m_storage->m_vector[i];
+        JSValue value = storage->m_vector[i].get();
         ASSERT(!value.isUndefined());
         values[i].first = value;
     }
 
         ASSERT(!value.isUndefined());
         values[i].first = value;
     }
 
-    // FIXME: While calling these toString functions, the array could be mutated.
-    // In that case, objects pointed to by values in this vector might get garbage-collected!
-
     // FIXME: The following loop continues to call toString on subsequent values even after
     // a toString call raises an exception.
 
     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
         values[i].second = values[i].first.toString(exec);
 
     // FIXME: The following loop continues to call toString on subsequent values even after
     // a toString call raises an exception.
 
     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
         values[i].second = values[i].first.toString(exec);
 
-    if (exec->hadException())
+    if (exec->hadException()) {
+        Heap::heap(this)->popTempSortVector(&values);
         return;
         return;
+    }
 
     // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
     // than O(N log N).
 
     // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
     // than O(N log N).
@@ -722,12 +969,19 @@ void JSArray::sort(ExecState* exec)
     qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 #endif
 
     qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 #endif
 
-    // FIXME: If the toString function changed the length of the array, this might be
-    // modifying the vector incorrectly.
+    // If the toString function changed the length of the array or vector storage,
+    // increase the length to handle the orignal number of actual values.
+    if (m_vectorLength < lengthNotIncludingUndefined)
+        increaseVectorLength(lengthNotIncludingUndefined);
+    if (storage->m_length < lengthNotIncludingUndefined)
+        storage->m_length = lengthNotIncludingUndefined;
 
 
+    JSGlobalData& globalData = exec->globalData();
     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
-        m_storage->m_vector[i] = values[i].first;
+        storage->m_vector[i].set(globalData, this, values[i].first);
 
 
+    Heap::heap(this)->popTempSortVector(&values);
+    
     checkConsistency(SortConsistencyCheck);
 }
 
     checkConsistency(SortConsistencyCheck);
 }
 
@@ -793,7 +1047,7 @@ struct AVLTreeAbstractorForArrayCompare {
             m_cachedCall->setThis(m_globalThisValue);
             m_cachedCall->setArgument(0, va);
             m_cachedCall->setArgument(1, vb);
             m_cachedCall->setThis(m_globalThisValue);
             m_cachedCall->setArgument(0, va);
             m_cachedCall->setArgument(1, vb);
-            compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame());
+            compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame(m_exec));
         } else {
             MarkedArgumentBuffer arguments;
             arguments.append(va);
         } else {
             MarkedArgumentBuffer arguments;
             arguments.append(va);
@@ -813,18 +1067,21 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType,
 {
     checkConsistency();
 
 {
     checkConsistency();
 
+    ArrayStorage* storage = m_storage;
+
     // FIXME: This ignores exceptions raised in the compare function or in toNumber.
 
     // The maximum tree depth is compiled in - but the caller is clearly up to no good
     // if a larger array is passed.
     // FIXME: This ignores exceptions raised in the compare function or in toNumber.
 
     // The maximum tree depth is compiled in - but the caller is clearly up to no good
     // if a larger array is passed.
-    ASSERT(m_storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
-    if (m_storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
+    ASSERT(storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
+    if (storage->m_length > static_cast<unsigned>(std::numeric_limits<int>::max()))
         return;
 
         return;
 
-    if (!m_storage->m_length)
-        return;
+    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
+    unsigned nodeCount = usedVectorLength + (storage->m_sparseValueMap ? storage->m_sparseValueMap->size() : 0);
 
 
-    unsigned usedVectorLength = min(m_storage->m_length, m_storage->m_vectorLength);
+    if (!nodeCount)
+        return;
 
     AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
     tree.abstractor().m_exec = exec;
 
     AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
     tree.abstractor().m_exec = exec;
@@ -832,10 +1089,10 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType,
     tree.abstractor().m_compareCallType = callType;
     tree.abstractor().m_compareCallData = &callData;
     tree.abstractor().m_globalThisValue = exec->globalThisValue();
     tree.abstractor().m_compareCallType = callType;
     tree.abstractor().m_compareCallData = &callData;
     tree.abstractor().m_globalThisValue = exec->globalThisValue();
-    tree.abstractor().m_nodes.resize(usedVectorLength + (m_storage->m_sparseValueMap ? m_storage->m_sparseValueMap->size() : 0));
+    tree.abstractor().m_nodes.grow(nodeCount);
 
     if (callType == CallTypeJS)
 
     if (callType == CallTypeJS)
-        tree.abstractor().m_cachedCall.set(new CachedCall(exec, asFunction(compareFunction), 2, exec->exceptionSlot()));
+        tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, asFunction(compareFunction), 2));
 
     if (!tree.abstractor().m_nodes.begin()) {
         throwOutOfMemoryError(exec);
 
     if (!tree.abstractor().m_nodes.begin()) {
         throwOutOfMemoryError(exec);
@@ -850,14 +1107,14 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType,
 
     // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
     for (; numDefined < usedVectorLength; ++numDefined) {
 
     // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
     for (; numDefined < usedVectorLength; ++numDefined) {
-        JSValue v = m_storage->m_vector[numDefined];
+        JSValue v = storage->m_vector[numDefined].get();
         if (!v || v.isUndefined())
             break;
         tree.abstractor().m_nodes[numDefined].value = v;
         tree.insert(numDefined);
     }
     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
         if (!v || v.isUndefined())
             break;
         tree.abstractor().m_nodes[numDefined].value = v;
         tree.insert(numDefined);
     }
     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
-        JSValue v = m_storage->m_vector[i];
+        JSValue v = storage->m_vector[i].get();
         if (v) {
             if (v.isUndefined())
                 ++numUndefined;
         if (v) {
             if (v.isUndefined())
                 ++numUndefined;
@@ -871,25 +1128,27 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType,
 
     unsigned newUsedVectorLength = numDefined + numUndefined;
 
 
     unsigned newUsedVectorLength = numDefined + numUndefined;
 
-    if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
+    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
         newUsedVectorLength += map->size();
         newUsedVectorLength += map->size();
-        if (newUsedVectorLength > m_storage->m_vectorLength) {
+        if (newUsedVectorLength > m_vectorLength) {
             // Check that it is possible to allocate an array large enough to hold all the entries.
             if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) {
                 throwOutOfMemoryError(exec);
                 return;
             }
         }
             // Check that it is possible to allocate an array large enough to hold all the entries.
             if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) {
                 throwOutOfMemoryError(exec);
                 return;
             }
         }
+        
+        storage = m_storage;
 
         SparseArrayValueMap::iterator end = map->end();
         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
 
         SparseArrayValueMap::iterator end = map->end();
         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
-            tree.abstractor().m_nodes[numDefined].value = it->second;
+            tree.abstractor().m_nodes[numDefined].value = it->second.get();
             tree.insert(numDefined);
             ++numDefined;
         }
 
         delete map;
             tree.insert(numDefined);
             ++numDefined;
         }
 
         delete map;
-        m_storage->m_sparseValueMap = 0;
+        storage->m_sparseValueMap = 0;
     }
 
     ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
     }
 
     ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
@@ -900,45 +1159,58 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType,
     // Copy the values back into m_storage.
     AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
     iter.start_iter_least(tree);
     // Copy the values back into m_storage.
     AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
     iter.start_iter_least(tree);
+    JSGlobalData& globalData = exec->globalData();
     for (unsigned i = 0; i < numDefined; ++i) {
     for (unsigned i = 0; i < numDefined; ++i) {
-        m_storage->m_vector[i] = tree.abstractor().m_nodes[*iter].value;
+        storage->m_vector[i].set(globalData, this, tree.abstractor().m_nodes[*iter].value);
         ++iter;
     }
 
     // Put undefined values back in.
     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
         ++iter;
     }
 
     // Put undefined values back in.
     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
-        m_storage->m_vector[i] = jsUndefined();
+        storage->m_vector[i].setUndefined();
 
     // Ensure that unused values in the vector are zeroed out.
     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
 
     // Ensure that unused values in the vector are zeroed out.
     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
-        m_storage->m_vector[i] = JSValue();
+        storage->m_vector[i].clear();
 
 
-    m_fastAccessCutoff = newUsedVectorLength;
-    m_storage->m_numValuesInVector = newUsedVectorLength;
+    storage->m_numValuesInVector = newUsedVectorLength;
 
     checkConsistency(SortConsistencyCheck);
 }
 
 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
 {
 
     checkConsistency(SortConsistencyCheck);
 }
 
 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
 {
-    unsigned fastAccessLength = min(m_storage->m_length, m_fastAccessCutoff);
+    ArrayStorage* storage = m_storage;
+
+    WriteBarrier<Unknown>* vector = storage->m_vector;
+    unsigned vectorEnd = min(storage->m_length, m_vectorLength);
     unsigned i = 0;
     unsigned i = 0;
-    for (; i < fastAccessLength; ++i)
-        args.append(getIndex(i));
-    for (; i < m_storage->m_length; ++i)
+    for (; i < vectorEnd; ++i) {
+        WriteBarrier<Unknown>& v = vector[i];
+        if (!v)
+            break;
+        args.append(v.get());
+    }
+
+    for (; i < storage->m_length; ++i)
         args.append(get(exec, i));
 }
 
 void JSArray::copyToRegisters(ExecState* exec, Register* buffer, uint32_t maxSize)
 {
         args.append(get(exec, i));
 }
 
 void JSArray::copyToRegisters(ExecState* exec, Register* buffer, uint32_t maxSize)
 {
-    ASSERT(m_storage->m_length == maxSize);
+    ASSERT(m_storage->m_length >= maxSize);
     UNUSED_PARAM(maxSize);
     UNUSED_PARAM(maxSize);
-    unsigned fastAccessLength = min(m_storage->m_length, m_fastAccessCutoff);
+    WriteBarrier<Unknown>* vector = m_storage->m_vector;
+    unsigned vectorEnd = min(maxSize, m_vectorLength);
     unsigned i = 0;
     unsigned i = 0;
-    for (; i < fastAccessLength; ++i)
-        buffer[i] = getIndex(i);
-    uint32_t size = m_storage->m_length;
-    for (; i < size; ++i)
+    for (; i < vectorEnd; ++i) {
+        WriteBarrier<Unknown>& v = vector[i];
+        if (!v)
+            break;
+        buffer[i] = v.get();
+    }
+
+    for (; i < maxSize; ++i)
         buffer[i] = get(exec, i);
 }
 
         buffer[i] = get(exec, i);
 }
 
@@ -948,23 +1220,24 @@ unsigned JSArray::compactForSorting()
 
     ArrayStorage* storage = m_storage;
 
 
     ArrayStorage* storage = m_storage;
 
-    unsigned usedVectorLength = min(m_storage->m_length, storage->m_vectorLength);
+    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
 
     unsigned numDefined = 0;
     unsigned numUndefined = 0;
 
     for (; numDefined < usedVectorLength; ++numDefined) {
 
     unsigned numDefined = 0;
     unsigned numUndefined = 0;
 
     for (; numDefined < usedVectorLength; ++numDefined) {
-        JSValue v = storage->m_vector[numDefined];
+        JSValue v = storage->m_vector[numDefined].get();
         if (!v || v.isUndefined())
             break;
     }
         if (!v || v.isUndefined())
             break;
     }
+
     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
-        JSValue v = storage->m_vector[i];
+        JSValue v = storage->m_vector[i].get();
         if (v) {
             if (v.isUndefined())
                 ++numUndefined;
             else
         if (v) {
             if (v.isUndefined())
                 ++numUndefined;
             else
-                storage->m_vector[numDefined++] = v;
+                storage->m_vector[numDefined++].setWithoutWriteBarrier(v);
         }
     }
 
         }
     }
 
@@ -972,28 +1245,28 @@ unsigned JSArray::compactForSorting()
 
     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
         newUsedVectorLength += map->size();
 
     if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
         newUsedVectorLength += map->size();
-        if (newUsedVectorLength > storage->m_vectorLength) {
+        if (newUsedVectorLength > m_vectorLength) {
             // Check that it is possible to allocate an array large enough to hold all the entries - if not,
             // exception is thrown by caller.
             if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength))
                 return 0;
             // Check that it is possible to allocate an array large enough to hold all the entries - if not,
             // exception is thrown by caller.
             if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength))
                 return 0;
+
             storage = m_storage;
         }
 
         SparseArrayValueMap::iterator end = map->end();
         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
             storage = m_storage;
         }
 
         SparseArrayValueMap::iterator end = map->end();
         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
-            storage->m_vector[numDefined++] = it->second;
+            storage->m_vector[numDefined++].setWithoutWriteBarrier(it->second.get());
 
         delete map;
         storage->m_sparseValueMap = 0;
     }
 
     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
 
         delete map;
         storage->m_sparseValueMap = 0;
     }
 
     for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
-        storage->m_vector[i] = jsUndefined();
+        storage->m_vector[i].setUndefined();
     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
-        storage->m_vector[i] = JSValue();
+        storage->m_vector[i].clear();
 
 
-    m_fastAccessCutoff = newUsedVectorLength;
     storage->m_numValuesInVector = newUsedVectorLength;
 
     checkConsistency(SortConsistencyCheck);
     storage->m_numValuesInVector = newUsedVectorLength;
 
     checkConsistency(SortConsistencyCheck);
@@ -1001,78 +1274,55 @@ unsigned JSArray::compactForSorting()
     return numDefined;
 }
 
     return numDefined;
 }
 
-void* JSArray::lazyCreationData()
+void* JSArray::subclassData() const
 {
 {
-    return m_storage->lazyCreationData;
+    return m_storage->subclassData;
 }
 
 }
 
-void JSArray::setLazyCreationData(void* d)
+void JSArray::setSubclassData(void* d)
 {
 {
-    m_storage->lazyCreationData = d;
+    m_storage->subclassData = d;
 }
 
 #if CHECK_ARRAY_CONSISTENCY
 
 void JSArray::checkConsistency(ConsistencyCheckType type)
 {
 }
 
 #if CHECK_ARRAY_CONSISTENCY
 
 void JSArray::checkConsistency(ConsistencyCheckType type)
 {
-    ASSERT(m_storage);
-    if (type == SortConsistencyCheck)
-        ASSERT(!m_storage->m_sparseValueMap);
+    ArrayStorage* storage = m_storage;
 
 
-    ASSERT(m_fastAccessCutoff <= m_storage->m_length);
-    ASSERT(m_fastAccessCutoff <= m_storage->m_numValuesInVector);
+    ASSERT(storage);
+    if (type == SortConsistencyCheck)
+        ASSERT(!storage->m_sparseValueMap);
 
     unsigned numValuesInVector = 0;
 
     unsigned numValuesInVector = 0;
-    for (unsigned i = 0; i < m_storage->m_vectorLength; ++i) {
-        if (JSValue value = m_storage->m_vector[i]) {
-            ASSERT(i < m_storage->m_length);
+    for (unsigned i = 0; i < m_vectorLength; ++i) {
+        if (JSValue value = storage->m_vector[i]) {
+            ASSERT(i < storage->m_length);
             if (type != DestructorConsistencyCheck)
             if (type != DestructorConsistencyCheck)
-                value->type(); // Likely to crash if the object was deallocated.
+                value.isUndefined(); // Likely to crash if the object was deallocated.
             ++numValuesInVector;
         } else {
             ++numValuesInVector;
         } else {
-            ASSERT(i >= m_fastAccessCutoff);
             if (type == SortConsistencyCheck)
             if (type == SortConsistencyCheck)
-                ASSERT(i >= m_storage->m_numValuesInVector);
+                ASSERT(i >= storage->m_numValuesInVector);
         }
     }
         }
     }
-    ASSERT(numValuesInVector == m_storage->m_numValuesInVector);
+    ASSERT(numValuesInVector == storage->m_numValuesInVector);
+    ASSERT(numValuesInVector <= storage->m_length);
 
 
-    if (m_storage->m_sparseValueMap) {
-        SparseArrayValueMap::iterator end = m_storage->m_sparseValueMap->end();
-        for (SparseArrayValueMap::iterator it = m_storage->m_sparseValueMap->begin(); it != end; ++it) {
+    if (storage->m_sparseValueMap) {
+        SparseArrayValueMap::iterator end = storage->m_sparseValueMap->end();
+        for (SparseArrayValueMap::iterator it = storage->m_sparseValueMap->begin(); it != end; ++it) {
             unsigned index = it->first;
             unsigned index = it->first;
-            ASSERT(index < m_storage->m_length);
-            ASSERT(index >= m_storage->m_vectorLength);
+            ASSERT(index < storage->m_length);
+            ASSERT(index >= storage->m_vectorLength);
             ASSERT(index <= MAX_ARRAY_INDEX);
             ASSERT(it->second);
             if (type != DestructorConsistencyCheck)
             ASSERT(index <= MAX_ARRAY_INDEX);
             ASSERT(it->second);
             if (type != DestructorConsistencyCheck)
-                it->second->type(); // Likely to crash if the object was deallocated.
+                it->second.isUndefined(); // Likely to crash if the object was deallocated.
         }
     }
 }
 
 #endif
 
         }
     }
 }
 
 #endif
 
-JSArray* constructEmptyArray(ExecState* exec)
-{
-    return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure());
-}
-
-JSArray* constructEmptyArray(ExecState* exec, unsigned initialLength)
-{
-    return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure(), initialLength);
-}
-
-JSArray* constructArray(ExecState* exec, JSValue singleItemValue)
-{
-    MarkedArgumentBuffer values;
-    values.append(singleItemValue);
-    return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure(), values);
-}
-
-JSArray* constructArray(ExecState* exec, const ArgList& values)
-{
-    return new (exec) JSArray(exec->lexicalGlobalObject()->arrayStructure(), values);
-}
-
 } // namespace JSC
 } // namespace JSC
mirror of JavaScriptCore