JavaScriptCore-7600.1.4.13.1.tar.gz

[apple/javascriptcore.git] / runtime / JSArray.cpp

diff --git a/runtime/JSArray.cpp b/runtime/JSArray.cpp
index 708ef99a27e3e878b780bda0eeedae2a67413fc0..f4bc093deedf1a176a369cde6aa97347602fea08 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, 2012, 2013 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)
  *


@@ -24,711 +24,1267 @@
 #include "JSArray.h"
 
 #include "ArrayPrototype.h"
 #include "JSArray.h"
 
 #include "ArrayPrototype.h"

+#include "ButterflyInlines.h"

 #include "CachedCall.h"
 #include "CachedCall.h"

+#include "CopiedSpace.h"
+#include "Error.h"
+#include "Executable.h"
+#include "GetterSetter.h"
+#include "IndexingHeaderInlines.h"
+#include "JSCInlines.h"

 #include "PropertyNameArray.h"
 #include "PropertyNameArray.h"

+#include "Reject.h"

 #include <wtf/AVLTree.h>
 #include <wtf/Assertions.h>
 #include <wtf/OwnPtr.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;
 
 namespace JSC {
 
 
 using namespace std;
 using namespace WTF;
 
 namespace JSC {
 

-ASSERT_CLASS_FITS_IN_CELL(JSArray);
-
-// Overview of JSArray
-//
-// Properties of JSArray objects may be stored in one of three locations:
-//   * The regular JSObject property map.
-//   * A storage vector.
-//   * A sparse map of array entries.
-//
-// Properties with non-numeric identifiers, with identifiers that are not representable
-// as an unsigned integer, or where the value is greater than  MAX_ARRAY_INDEX
-// (specifically, this is only one property - the value 0xFFFFFFFFU as an unsigned 32-bit
-// integer) are not considered array indices and will be stored in the JSObject property map.
-//
-// All properties with a numeric identifer, representable as an unsigned integer i,
-// where (i <= MAX_ARRAY_INDEX), are an array index and will be stored in either the
-// storage vector or the sparse map.  An array index i will be handled in the following
-// fashion:
-//
-//   * Where (i < MIN_SPARSE_ARRAY_INDEX) the value will be stored in the storage vector.
-//   * Where (MIN_SPARSE_ARRAY_INDEX <= i <= MAX_STORAGE_VECTOR_INDEX) the value will either
-//     be stored in the storage vector or in the sparse array, depending on the density of
-//     data that would be stored in the vector (a vector being used where at least
-//     (1 / minDensityMultiplier) of the entries would be populated).
-//   * Where (MAX_STORAGE_VECTOR_INDEX < i <= MAX_ARRAY_INDEX) the value will always be stored
-//     in the sparse array.
-
-// 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(JSValue)) +
-// (vectorLength * sizeof(JSValue)) must be <= 0xFFFFFFFFU (which is maximum value of size_t).
-#define MAX_STORAGE_VECTOR_LENGTH static_cast<unsigned>((0xFFFFFFFFU - (sizeof(ArrayStorage) - sizeof(JSValue))) / sizeof(JSValue))
-
-// 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)
-// 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
-#define MAX_ARRAY_INDEX 0xFFFFFFFEU
-
-// 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};
-
-static inline size_t storageSize(unsigned vectorLength)
-{
-    ASSERT(vectorLength <= MAX_STORAGE_VECTOR_LENGTH);
+STATIC_ASSERT_IS_TRIVIALLY_DESTRUCTIBLE(JSArray);

 
 

-    // 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(JSValue)) + (vectorLength * sizeof(JSValue));
-    // 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(JSValue))) / sizeof(JSValue) == vectorLength) && (size >= (sizeof(ArrayStorage) - sizeof(JSValue))));
+const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0, CREATE_METHOD_TABLE(JSArray)};

 
 

-    return size;
+Butterfly* createArrayButterflyInDictionaryIndexingMode(
+    VM& vm, JSCell* intendedOwner, unsigned initialLength)
+{
+    Butterfly* butterfly = Butterfly::create(
+        vm, intendedOwner, 0, 0, true, IndexingHeader(), ArrayStorage::sizeFor(0));
+    ArrayStorage* storage = butterfly->arrayStorage();
+    storage->setLength(initialLength);
+    storage->setVectorLength(0);
+    storage->m_indexBias = 0;
+    storage->m_sparseMap.clear();
+    storage->m_numValuesInVector = 0;
+    return butterfly;

 }
 
 }
 

-static inline unsigned increasedVectorLength(unsigned newLength)
+void JSArray::setLengthWritable(ExecState* exec, bool writable)

 {
 {

-    ASSERT(newLength <= MAX_STORAGE_VECTOR_LENGTH);
+    ASSERT(isLengthWritable() || !writable);
+    if (!isLengthWritable() || writable)
+        return;

 
 

-    // 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);
+    enterDictionaryIndexingMode(exec->vm());

 
 

-    return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
+    SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get();
+    ASSERT(map);
+    map->setLengthIsReadOnly();

 }
 
 }
 

-static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
+// Defined in ES5.1 15.4.5.1
+bool JSArray::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, const PropertyDescriptor& descriptor, bool throwException)

 {
 {

-    return length / minDensityMultiplier <= numValues;
-}
-
-#if !CHECK_ARRAY_CONSISTENCY
+    JSArray* array = jsCast<JSArray*>(object);

 
 

-inline void JSArray::checkConsistency(ConsistencyCheckType)
-{
-}
+    // 3. If P is "length", then
+    if (propertyName == exec->propertyNames().length) {
+        // All paths through length definition call the default [[DefineOwnProperty]], hence:
+        // from ES5.1 8.12.9 7.a.
+        if (descriptor.configurablePresent() && descriptor.configurable())
+            return reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property.");
+        // from ES5.1 8.12.9 7.b.
+        if (descriptor.enumerablePresent() && descriptor.enumerable())
+            return reject(exec, throwException, "Attempting to change enumerable attribute of unconfigurable property.");
+
+        // a. If the [[Value]] field of Desc is absent, then
+        // a.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", Desc, and Throw as arguments.
+        if (descriptor.isAccessorDescriptor())
+            return reject(exec, throwException, "Attempting to change access mechanism for an unconfigurable property.");
+        // from ES5.1 8.12.9 10.a.
+        if (!array->isLengthWritable() && descriptor.writablePresent() && descriptor.writable())
+            return reject(exec, throwException, "Attempting to change writable attribute of unconfigurable property.");
+        // This descriptor is either just making length read-only, or changing nothing!
+        if (!descriptor.value()) {
+            if (descriptor.writablePresent())
+                array->setLengthWritable(exec, descriptor.writable());
+            return true;
+        }
+        
+        // b. Let newLenDesc be a copy of Desc.
+        // c. Let newLen be ToUint32(Desc.[[Value]]).
+        unsigned newLen = descriptor.value().toUInt32(exec);
+        // d. If newLen is not equal to ToNumber( Desc.[[Value]]), throw a RangeError exception.
+        if (newLen != descriptor.value().toNumber(exec)) {
+            exec->vm().throwException(exec, createRangeError(exec, "Invalid array length"));
+            return false;
+        }

 
 

-#endif
+        // Based on SameValue check in 8.12.9, this is always okay.
+        if (newLen == array->length()) {
+            if (descriptor.writablePresent())
+                array->setLengthWritable(exec, descriptor.writable());
+            return true;
+        }

 
 

-JSArray::JSArray(PassRefPtr<Structure> structure)
-    : JSObject(structure)
-{
-    unsigned initialCapacity = 0;
+        // e. Set newLenDesc.[[Value] to newLen.
+        // f. If newLen >= oldLen, then
+        // f.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments.
+        // g. Reject if oldLenDesc.[[Writable]] is false.
+        if (!array->isLengthWritable())
+            return reject(exec, throwException, "Attempting to change value of a readonly property.");
+        
+        // h. If newLenDesc.[[Writable]] is absent or has the value true, let newWritable be true.
+        // i. Else,
+        // i.i. Need to defer setting the [[Writable]] attribute to false in case any elements cannot be deleted.
+        // i.ii. Let newWritable be false.
+        // i.iii. Set newLenDesc.[[Writable] to true.
+        // j. Let succeeded be the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments.
+        // k. If succeeded is false, return false.
+        // l. While newLen < oldLen repeat,
+        // l.i. Set oldLen to oldLen – 1.
+        // l.ii. Let deleteSucceeded be the result of calling the [[Delete]] internal method of A passing ToString(oldLen) and false as arguments.
+        // l.iii. If deleteSucceeded is false, then
+        if (!array->setLength(exec, newLen, throwException)) {
+            // 1. Set newLenDesc.[[Value] to oldLen+1.
+            // 2. If newWritable is false, set newLenDesc.[[Writable] to false.
+            // 3. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and false as arguments.
+            // 4. Reject.
+            if (descriptor.writablePresent())
+                array->setLengthWritable(exec, descriptor.writable());
+            return false;
+        }

 
 

-    m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
-    m_storage->m_vectorLength = initialCapacity;
+        // m. If newWritable is false, then
+        // i. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length",
+        //    Property Descriptor{[[Writable]]: false}, and false as arguments. This call will always
+        //    return true.
+        if (descriptor.writablePresent())
+            array->setLengthWritable(exec, descriptor.writable());
+        // n. Return true.
+        return true;
+    }

 
 

-    m_fastAccessCutoff = 0;
+    // 4. Else if P is an array index (15.4), then
+    // a. Let index be ToUint32(P).
+    unsigned index = propertyName.asIndex();
+    if (index != PropertyName::NotAnIndex) {
+        // b. Reject if index >= oldLen and oldLenDesc.[[Writable]] is false.
+        if (index >= array->length() && !array->isLengthWritable())
+            return reject(exec, throwException, "Attempting to define numeric property on array with non-writable length property.");
+        // c. Let succeeded be the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing P, Desc, and false as arguments.
+        // d. Reject if succeeded is false.
+        // e. If index >= oldLen
+        // e.i. Set oldLenDesc.[[Value]] to index + 1.
+        // e.ii. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", oldLenDesc, and false as arguments. This call will always return true.
+        // f. Return true.
+        return array->defineOwnIndexedProperty(exec, index, descriptor, throwException);
+    }

 
 

-    checkConsistency();
+    return array->JSObject::defineOwnNonIndexProperty(exec, propertyName, descriptor, throwException);

 }
 
 }
 

-JSArray::JSArray(PassRefPtr<Structure> structure, unsigned initialLength)
-    : JSObject(structure)
+bool JSArray::getOwnPropertySlot(JSObject* object, ExecState* exec, PropertyName propertyName, PropertySlot& slot)

 {
 {

-    unsigned initialCapacity = min(initialLength, MIN_SPARSE_ARRAY_INDEX);
-
-    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
-    m_storage->m_length = initialLength;
-    m_storage->m_vectorLength = initialCapacity;
-    m_storage->m_numValuesInVector = 0;
-    m_storage->m_sparseValueMap = 0;
-    m_storage->lazyCreationData = 0;
+    JSArray* thisObject = jsCast<JSArray*>(object);
+    if (propertyName == exec->propertyNames().length) {
+        unsigned attributes = thisObject->isLengthWritable() ? DontDelete | DontEnum : DontDelete | DontEnum | ReadOnly;
+        slot.setValue(thisObject, attributes, jsNumber(thisObject->length()));
+        return true;
+    }

 
 

-    JSValue* vector = m_storage->m_vector;
-    for (size_t i = 0; i < initialCapacity; ++i)
-        vector[i] = JSValue();
+    return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);
+}

 
 

-    m_fastAccessCutoff = 0;
+// ECMA 15.4.5.1
+void JSArray::put(JSCell* cell, ExecState* exec, PropertyName propertyName, JSValue value, PutPropertySlot& slot)
+{
+    JSArray* thisObject = jsCast<JSArray*>(cell);

 
 

-    checkConsistency();
+    if (propertyName == exec->propertyNames().length) {
+        unsigned newLength = value.toUInt32(exec);
+        if (value.toNumber(exec) != static_cast<double>(newLength)) {
+            exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length")));
+            return;
+        }
+        thisObject->setLength(exec, newLength, slot.isStrictMode());
+        return;
+    }

 
 

-    Heap::heap(this)->reportExtraMemoryCost(initialCapacity * sizeof(JSValue));
+    JSObject::put(thisObject, exec, propertyName, value, slot);

 }
 
 }
 

-JSArray::JSArray(PassRefPtr<Structure> structure, const ArgList& list)
-    : JSObject(structure)
+bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, PropertyName propertyName)

 {
 {

-    unsigned initialCapacity = list.size();
-
-    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
-    m_storage->m_length = initialCapacity;
-    m_storage->m_vectorLength = initialCapacity;
-    m_storage->m_numValuesInVector = initialCapacity;
-    m_storage->m_sparseValueMap = 0;
-
-    size_t i = 0;
-    ArgList::const_iterator end = list.end();
-    for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
-        m_storage->m_vector[i] = *it;
+    JSArray* thisObject = jsCast<JSArray*>(cell);

 
 

-    m_fastAccessCutoff = initialCapacity;
+    if (propertyName == exec->propertyNames().length)
+        return false;

 
 

-    checkConsistency();
+    return JSObject::deleteProperty(thisObject, exec, propertyName);
+}

 
 

-    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity));
+static int compareKeysForQSort(const void* a, const void* b)
+{
+    unsigned da = *static_cast<const unsigned*>(a);
+    unsigned db = *static_cast<const unsigned*>(b);
+    return (da > db) - (da < db);

 }
 
 }
 

-JSArray::~JSArray()
+void JSArray::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)

 {
 {

-    checkConsistency(DestructorConsistencyCheck);
+    JSArray* thisObject = jsCast<JSArray*>(object);
+
+    if (mode == IncludeDontEnumProperties)
+        propertyNames.add(exec->propertyNames().length);

 
 

-    delete m_storage->m_sparseValueMap;
-    fastFree(m_storage);
+    JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode);

 }
 
 }
 

-bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
+// This method makes room in the vector, but leaves the new space for count slots uncleared.
+bool JSArray::unshiftCountSlowCase(VM& vm, bool addToFront, unsigned count)

 {
 {

-    ArrayStorage* storage = m_storage;
-
-    if (i >= storage->m_length) {
-        if (i > MAX_ARRAY_INDEX)
-            return getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
+    ArrayStorage* storage = ensureArrayStorage(vm);
+    Butterfly* butterfly = storage->butterfly();
+    unsigned propertyCapacity = structure(vm)->outOfLineCapacity();
+    unsigned propertySize = structure(vm)->outOfLineSize();
+
+    // If not, we should have handled this on the fast path.
+    ASSERT(!addToFront || count > storage->m_indexBias);
+
+    // Step 1:
+    // Gather 4 key metrics:
+    //  * usedVectorLength - how many entries are currently in the vector (conservative estimate - fewer may be in use in sparse vectors).
+    //  * requiredVectorLength - how many entries are will there be in the vector, after allocating space for 'count' more.
+    //  * currentCapacity - what is the current size of the vector, including any pre-capacity.
+    //  * desiredCapacity - how large should we like to grow the vector to - based on 2x requiredVectorLength.
+
+    unsigned length = storage->length();
+    unsigned usedVectorLength = min(storage->vectorLength(), length);
+    ASSERT(usedVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
+    // Check that required vector length is possible, in an overflow-safe fashion.
+    if (count > MAX_STORAGE_VECTOR_LENGTH - usedVectorLength)

         return false;
         return false;

+    unsigned requiredVectorLength = usedVectorLength + count;
+    ASSERT(requiredVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
+    // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH.
+    ASSERT(storage->vectorLength() <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - storage->vectorLength()) >= storage->m_indexBias);
+    unsigned currentCapacity = storage->vectorLength() + storage->m_indexBias;
+    // The calculation of desiredCapacity won't overflow, due to the range of MAX_STORAGE_VECTOR_LENGTH.
+    unsigned desiredCapacity = min(MAX_STORAGE_VECTOR_LENGTH, max(BASE_VECTOR_LEN, requiredVectorLength) << 1);
+
+    // Step 2:
+    // We're either going to choose to allocate a new ArrayStorage, or we're going to reuse the existing one.
+
+    DeferGC deferGC(vm.heap);
+    void* newAllocBase = 0;
+    unsigned newStorageCapacity;
+    // If the current storage array is sufficiently large (but not too large!) then just keep using it.
+    if (currentCapacity > desiredCapacity && isDenseEnoughForVector(currentCapacity, requiredVectorLength)) {
+        newAllocBase = butterfly->base(structure(vm));
+        newStorageCapacity = currentCapacity;
+    } else {
+        size_t newSize = Butterfly::totalSize(0, propertyCapacity, true, ArrayStorage::sizeFor(desiredCapacity));
+        if (!vm.heap.tryAllocateStorage(this, newSize, &newAllocBase))
+            return false;
+        newStorageCapacity = desiredCapacity;

     }
 
     }
 

-    if (i < storage->m_vectorLength) {
-        JSValue& valueSlot = storage->m_vector[i];
-        if (valueSlot) {
-            slot.setValueSlot(&valueSlot);
-            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);
-                return true;
-            }
-        }
+    // Step 3:
+    // Work out where we're going to move things to.
+
+    // Determine how much of the vector to use as pre-capacity, and how much as post-capacity.
+    // If we're adding to the end, we'll add all the new space to the end.
+    // If the vector had no free post-capacity (length >= m_vectorLength), don't give it any.
+    // If it did, we calculate the amount that will remain based on an atomic decay - leave the
+    // vector with half the post-capacity it had previously.
+    unsigned postCapacity = 0;
+    if (!addToFront)
+        postCapacity = max(newStorageCapacity - requiredVectorLength, count);
+    else if (length < storage->vectorLength()) {
+        // Atomic decay, + the post-capacity cannot be greater than what is available.
+        postCapacity = min((storage->vectorLength() - length) >> 1, newStorageCapacity - requiredVectorLength);
+        // If we're moving contents within the same allocation, the post-capacity is being reduced.
+        ASSERT(newAllocBase != butterfly->base(structure(vm)) || postCapacity < storage->vectorLength() - length);

     }
 
     }
 

-    return false;
-}
+    unsigned newVectorLength = requiredVectorLength + postCapacity;
+    unsigned newIndexBias = newStorageCapacity - newVectorLength;

 
 

-bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
-{
-    if (propertyName == exec->propertyNames().length) {
-        slot.setValue(jsNumber(exec, length()));
-        return true;
+    Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, newIndexBias, propertyCapacity);
+
+    if (addToFront) {
+        ASSERT(count + usedVectorLength <= newVectorLength);
+        memmove(newButterfly->arrayStorage()->m_vector + count, storage->m_vector, sizeof(JSValue) * usedVectorLength);
+        memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
+    } else if ((newAllocBase != butterfly->base(structure(vm))) || (newIndexBias != storage->m_indexBias)) {
+        memmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
+        memmove(newButterfly->arrayStorage()->m_vector, storage->m_vector, sizeof(JSValue) * usedVectorLength);
+
+        WriteBarrier<Unknown>* newVector = newButterfly->arrayStorage()->m_vector;
+        for (unsigned i = requiredVectorLength; i < newVectorLength; i++)
+            newVector[i].clear();

     }
 
     }
 

-    bool isArrayIndex;
-    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
-    if (isArrayIndex)
-        return JSArray::getOwnPropertySlot(exec, i, slot);
+    newButterfly->arrayStorage()->setVectorLength(newVectorLength);
+    newButterfly->arrayStorage()->m_indexBias = newIndexBias;
+    setButterflyWithoutChangingStructure(vm, newButterfly);

 
 

-    return JSObject::getOwnPropertySlot(exec, propertyName, slot);
+    return true;

 }
 
 }
 

-// ECMA 15.4.5.1
-void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
+bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, bool throwException, ArrayStorage* storage)

 {
 {

-    bool isArrayIndex;
-    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
-    if (isArrayIndex) {
-        put(exec, i, value);
-        return;
+    unsigned length = storage->length();
+
+    // If the length is read only then we enter sparse mode, so should enter the following 'if'.
+    ASSERT(isLengthWritable() || storage->m_sparseMap);
+
+    if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
+        // Fail if the length is not writable.
+        if (map->lengthIsReadOnly())
+            return reject(exec, throwException, StrictModeReadonlyPropertyWriteError);
+
+        if (newLength < length) {
+            // Copy any keys we might be interested in into a vector.
+            Vector<unsigned, 0, UnsafeVectorOverflow> keys;
+            keys.reserveInitialCapacity(min(map->size(), static_cast<size_t>(length - newLength)));
+            SparseArrayValueMap::const_iterator end = map->end();
+            for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
+                unsigned index = static_cast<unsigned>(it->key);
+                if (index < length && index >= newLength)
+                    keys.append(index);
+            }
+
+            // Check if the array is in sparse mode. If so there may be non-configurable
+            // properties, so we have to perform deletion with caution, if not we can
+            // delete values in any order.
+            if (map->sparseMode()) {
+                qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort);
+                unsigned i = keys.size();
+                while (i) {
+                    unsigned index = keys[--i];
+                    SparseArrayValueMap::iterator it = map->find(index);
+                    ASSERT(it != map->notFound());
+                    if (it->value.attributes & DontDelete) {
+                        storage->setLength(index + 1);
+                        return reject(exec, throwException, "Unable to delete property.");
+                    }
+                    map->remove(it);
+                }
+            } else {
+                for (unsigned i = 0; i < keys.size(); ++i)
+                    map->remove(keys[i]);
+                if (map->isEmpty())
+                    deallocateSparseIndexMap();
+            }
+        }

     }
 
     }
 

-    if (propertyName == exec->propertyNames().length) {
-        unsigned newLength = value.toUInt32(exec);
-        if (value.toNumber(exec) != static_cast<double>(newLength)) {
-            throwError(exec, RangeError, "Invalid array length.");
-            return;
+    if (newLength < length) {
+        // Delete properties from the vector.
+        unsigned usedVectorLength = min(length, storage->vectorLength());
+        for (unsigned i = newLength; i < usedVectorLength; ++i) {
+            WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
+            bool hadValue = valueSlot;
+            valueSlot.clear();
+            storage->m_numValuesInVector -= hadValue;

         }
         }

-        setLength(newLength);
-        return;

     }
 
     }
 

-    JSObject::put(exec, propertyName, value, slot);
+    storage->setLength(newLength);
+
+    return true;

 }
 
 }
 

-void JSArray::put(ExecState* exec, unsigned i, JSValue value)
+bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)

 {
 {

-    checkConsistency();
-
-    unsigned length = m_storage->m_length;
-    if (i >= length && i <= MAX_ARRAY_INDEX) {
-        length = i + 1;
-        m_storage->m_length = length;
+    switch (indexingType()) {
+    case ArrayClass:
+        if (!newLength)
+            return true;
+        if (newLength >= MIN_SPARSE_ARRAY_INDEX) {
+            return setLengthWithArrayStorage(
+                exec, newLength, throwException,
+                convertContiguousToArrayStorage(exec->vm()));
+        }
+        createInitialUndecided(exec->vm(), newLength);
+        return true;
+        
+    case ArrayWithUndecided:
+    case ArrayWithInt32:
+    case ArrayWithDouble:
+    case ArrayWithContiguous:
+        if (newLength == m_butterfly->publicLength())
+            return true;
+        if (newLength >= MAX_ARRAY_INDEX // This case ensures that we can do fast push.
+            || (newLength >= MIN_SPARSE_ARRAY_INDEX
+                && !isDenseEnoughForVector(newLength, countElements()))) {
+            return setLengthWithArrayStorage(
+                exec, newLength, throwException,
+                ensureArrayStorage(exec->vm()));
+        }
+        if (newLength > m_butterfly->publicLength()) {
+            ensureLength(exec->vm(), newLength);
+            return true;
+        }
+        if (indexingType() == ArrayWithDouble) {
+            for (unsigned i = m_butterfly->publicLength(); i-- > newLength;)
+                m_butterfly->contiguousDouble()[i] = PNaN;
+        } else {
+            for (unsigned i = m_butterfly->publicLength(); i-- > newLength;)
+                m_butterfly->contiguous()[i].clear();
+        }
+        m_butterfly->setPublicLength(newLength);
+        return true;
+        
+    case ArrayWithArrayStorage:
+    case ArrayWithSlowPutArrayStorage:
+        return setLengthWithArrayStorage(exec, newLength, throwException, arrayStorage());
+        
+    default:
+        CRASH();
+        return false;

     }
     }

+}

 
 

-    if (i < m_storage->m_vectorLength) {
-        JSValue& valueSlot = m_storage->m_vector[i];
-        if (valueSlot) {
-            valueSlot = value;
-            checkConsistency();
-            return;
+JSValue JSArray::pop(ExecState* exec)
+{
+    switch (indexingType()) {
+    case ArrayClass:
+        return jsUndefined();
+        
+    case ArrayWithUndecided:
+        if (!m_butterfly->publicLength())
+            return jsUndefined();
+        // We have nothing but holes. So, drop down to the slow version.
+        break;
+        
+    case ArrayWithInt32:
+    case ArrayWithContiguous: {
+        unsigned length = m_butterfly->publicLength();
+        
+        if (!length--)
+            return jsUndefined();
+        
+        RELEASE_ASSERT(length < m_butterfly->vectorLength());
+        JSValue value = m_butterfly->contiguous()[length].get();
+        if (value) {
+            m_butterfly->contiguous()[length].clear();
+            m_butterfly->setPublicLength(length);
+            return value;

         }
         }

-        valueSlot = value;
-        if (++m_storage->m_numValuesInVector == m_storage->m_length)
-            m_fastAccessCutoff = m_storage->m_length;
-        checkConsistency();
-        return;
+        break;
+    }
+        
+    case ArrayWithDouble: {
+        unsigned length = m_butterfly->publicLength();
+        
+        if (!length--)
+            return jsUndefined();
+        
+        RELEASE_ASSERT(length < m_butterfly->vectorLength());
+        double value = m_butterfly->contiguousDouble()[length];
+        if (value == value) {
+            m_butterfly->contiguousDouble()[length] = PNaN;
+            m_butterfly->setPublicLength(length);
+            return JSValue(JSValue::EncodeAsDouble, value);
+        }
+        break;

     }
     }

+        
+    case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
+        ArrayStorage* storage = m_butterfly->arrayStorage();
+    
+        unsigned length = storage->length();
+        if (!length) {
+            if (!isLengthWritable())
+                throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
+            return jsUndefined();
+        }

 
 

-    putSlowCase(exec, i, value);
+        unsigned index = length - 1;
+        if (index < storage->vectorLength()) {
+            WriteBarrier<Unknown>& valueSlot = storage->m_vector[index];
+            if (valueSlot) {
+                --storage->m_numValuesInVector;
+                JSValue element = valueSlot.get();
+                valueSlot.clear();
+            
+                RELEASE_ASSERT(isLengthWritable());
+                storage->setLength(index);
+                return element;
+            }
+        }
+        break;
+    }
+        
+    default:
+        CRASH();
+        return JSValue();
+    }
+    
+    unsigned index = getArrayLength() - 1;
+    // Let element be the result of calling the [[Get]] internal method of O with argument indx.
+    JSValue element = get(exec, index);
+    if (exec->hadException())
+        return jsUndefined();
+    // Call the [[Delete]] internal method of O with arguments indx and true.
+    if (!deletePropertyByIndex(this, exec, index)) {
+        throwTypeError(exec, "Unable to delete property.");
+        return jsUndefined();
+    }
+    // Call the [[Put]] internal method of O with arguments "length", indx, and true.
+    setLength(exec, index, true);
+    // Return element.
+    return element;

 }
 
 }
 

-NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
+// Push & putIndex are almost identical, with two small differences.
+//  - we always are writing beyond the current array bounds, so it is always necessary to update m_length & m_numValuesInVector.
+//  - pushing to an array of length 2^32-1 stores the property, but throws a range error.
+void JSArray::push(ExecState* exec, JSValue value)

 {
 {

-    ArrayStorage* storage = m_storage;
-    SparseArrayValueMap* map = storage->m_sparseValueMap;
-
-    if (i >= MIN_SPARSE_ARRAY_INDEX) {
-        if (i > MAX_ARRAY_INDEX) {
-            PutPropertySlot slot;
-            put(exec, Identifier::from(exec, i), value, slot);
+    switch (indexingType()) {
+    case ArrayClass: {
+        createInitialUndecided(exec->vm(), 0);
+        FALLTHROUGH;
+    }
+        
+    case ArrayWithUndecided: {
+        convertUndecidedForValue(exec->vm(), value);
+        push(exec, value);
+        return;
+    }
+        
+    case ArrayWithInt32: {
+        if (!value.isInt32()) {
+            convertInt32ForValue(exec->vm(), value);
+            push(exec, value);

             return;
         }
 
             return;
         }
 

-        // 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.
-        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);
+        unsigned length = m_butterfly->publicLength();
+        ASSERT(length <= m_butterfly->vectorLength());
+        if (length < m_butterfly->vectorLength()) {
+            m_butterfly->contiguousInt32()[length].setWithoutWriteBarrier(value);
+            m_butterfly->setPublicLength(length + 1);
+            return;
+        }
+        
+        if (length > MAX_ARRAY_INDEX) {
+            methodTable(exec->vm())->putByIndex(this, exec, length, value, true);
+            if (!exec->hadException())
+                exec->vm().throwException(exec, createRangeError(exec, "Invalid array length"));

             return;
         }
             return;
         }

+        
+        putByIndexBeyondVectorLengthWithoutAttributes<Int32Shape>(exec, length, value);
+        return;

     }
 
     }
 

-    // We have decided that we'll put the new item into the vector.
-    // Fast case is when there is no sparse map, so we can increase the vector size without moving values from it.
-    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;
-            checkConsistency();
-        } else
-            throwOutOfMemoryError(exec);
+    case ArrayWithContiguous: {
+        unsigned length = m_butterfly->publicLength();
+        ASSERT(length <= m_butterfly->vectorLength());
+        if (length < m_butterfly->vectorLength()) {
+            m_butterfly->contiguous()[length].set(exec->vm(), this, value);
+            m_butterfly->setPublicLength(length + 1);
+            return;
+        }
+        
+        if (length > MAX_ARRAY_INDEX) {
+            methodTable(exec->vm())->putByIndex(this, exec, length, value, true);
+            if (!exec->hadException())
+                exec->vm().throwException(exec, createRangeError(exec, "Invalid array length"));
+            return;
+        }
+        
+        putByIndexBeyondVectorLengthWithoutAttributes<ContiguousShape>(exec, length, value);

         return;
     }
         return;
     }

+        
+    case ArrayWithDouble: {
+        if (!value.isNumber()) {
+            convertDoubleToContiguous(exec->vm());
+            push(exec, value);
+            return;
+        }
+        double valueAsDouble = value.asNumber();
+        if (valueAsDouble != valueAsDouble) {
+            convertDoubleToContiguous(exec->vm());
+            push(exec, value);
+            return;
+        }

 
 

-    // 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)
-        newNumValuesInVector += map->contains(j);
-    if (i >= MIN_SPARSE_ARRAY_INDEX)
-        newNumValuesInVector -= map->contains(i);
-    if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
-        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);
-            for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
-                proposedNewNumValuesInVector += map->contains(j);
-            if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
-                break;
-            newVectorLength = proposedNewVectorLength;
-            newNumValuesInVector = proposedNewNumValuesInVector;
+        unsigned length = m_butterfly->publicLength();
+        ASSERT(length <= m_butterfly->vectorLength());
+        if (length < m_butterfly->vectorLength()) {
+            m_butterfly->contiguousDouble()[length] = valueAsDouble;
+            m_butterfly->setPublicLength(length + 1);
+            return;
+        }
+        
+        if (length > MAX_ARRAY_INDEX) {
+            methodTable(exec->vm())->putByIndex(this, exec, length, value, true);
+            if (!exec->hadException())
+                exec->vm().throwException(exec, createRangeError(exec, "Invalid array length"));
+            return;

         }
         }

+        
+        putByIndexBeyondVectorLengthWithoutAttributes<DoubleShape>(exec, length, value);
+        break;

     }
     }

-
-    storage = static_cast<ArrayStorage*>(tryFastRealloc(storage, storageSize(newVectorLength)));
-    if (!storage) {
-        throwOutOfMemoryError(exec);
-        return;
+        
+    case ArrayWithSlowPutArrayStorage: {
+        unsigned oldLength = length();
+        if (attemptToInterceptPutByIndexOnHole(exec, oldLength, value, true)) {
+            if (!exec->hadException() && oldLength < 0xFFFFFFFFu)
+                setLength(exec, oldLength + 1, true);
+            return;
+        }
+        FALLTHROUGH;

     }
     }

+        
+    case ArrayWithArrayStorage: {
+        ArrayStorage* storage = m_butterfly->arrayStorage();
+
+        // Fast case - push within vector, always update m_length & m_numValuesInVector.
+        unsigned length = storage->length();
+        if (length < storage->vectorLength()) {
+            storage->m_vector[length].set(exec->vm(), this, value);
+            storage->setLength(length + 1);
+            ++storage->m_numValuesInVector;
+            return;
+        }

 
 

-    unsigned vectorLength = storage->m_vectorLength;
-
-    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
+        // Pushing to an array of invalid length (2^31-1) stores the property, but throws a range error.
+        if (storage->length() > MAX_ARRAY_INDEX) {
+            methodTable(exec->vm())->putByIndex(this, exec, storage->length(), value, true);
+            // Per ES5.1 15.4.4.7 step 6 & 15.4.5.1 step 3.d.
+            if (!exec->hadException())
+                exec->vm().throwException(exec, createRangeError(exec, "Invalid array length"));
+            return;
+        }

 
 

-    if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
-        for (unsigned j = vectorLength; j < newVectorLength; ++j)
-            storage->m_vector[j] = JSValue();
-        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();
-        for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
-            storage->m_vector[j] = map->take(j);
+        // Handled the same as putIndex.
+        putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage);
+        break;
+    }
+        
+    default:
+        RELEASE_ASSERT_NOT_REACHED();

     }
     }

-
-    storage->m_vector[i] = value;
-
-    storage->m_vectorLength = newVectorLength;
-    storage->m_numValuesInVector = newNumValuesInVector;
-
-    m_storage = storage;
-
-    checkConsistency();

 }
 
 }
 

-bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName)
+bool JSArray::shiftCountWithArrayStorage(VM& vm, unsigned startIndex, unsigned count, ArrayStorage* storage)

 {
 {

-    bool isArrayIndex;
-    unsigned i = propertyName.toArrayIndex(&isArrayIndex);
-    if (isArrayIndex)
-        return deleteProperty(exec, i);
-
-    if (propertyName == exec->propertyNames().length)
+    unsigned oldLength = storage->length();
+    RELEASE_ASSERT(count <= oldLength);
+    
+    // If the array contains holes or is otherwise in an abnormal state,
+    // use the generic algorithm in ArrayPrototype.
+    if ((storage->hasHoles() && this->structure(vm)->holesMustForwardToPrototype(vm)) 
+        || inSparseIndexingMode() 
+        || shouldUseSlowPut(indexingType())) {

         return false;
         return false;

-
-    return JSObject::deleteProperty(exec, propertyName);
-}
-
-bool JSArray::deleteProperty(ExecState* exec, unsigned i)
-{
-    checkConsistency();
-
-    ArrayStorage* storage = m_storage;
-
-    if (i < storage->m_vectorLength) {
-        JSValue& valueSlot = storage->m_vector[i];
-        if (!valueSlot) {
-            checkConsistency();
-            return false;
-        }
-        valueSlot = JSValue();
-        --storage->m_numValuesInVector;
-        if (m_fastAccessCutoff > i)
-            m_fastAccessCutoff = i;
-        checkConsistency();
-        return true;

     }
 
     }
 

-    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
-        if (i >= MIN_SPARSE_ARRAY_INDEX) {
-            SparseArrayValueMap::iterator it = map->find(i);
-            if (it != map->end()) {
-                map->remove(it);
-                checkConsistency();
-                return true;
+    if (!oldLength)
+        return true;
+    
+    unsigned length = oldLength - count;
+    
+    storage->m_numValuesInVector -= count;
+    storage->setLength(length);
+    
+    unsigned vectorLength = storage->vectorLength();
+    if (!vectorLength)
+        return true;
+    
+    if (startIndex >= vectorLength)
+        return true;
+    
+    if (startIndex + count > vectorLength)
+        count = vectorLength - startIndex;
+    
+    unsigned usedVectorLength = min(vectorLength, oldLength);
+    
+    unsigned numElementsBeforeShiftRegion = startIndex;
+    unsigned firstIndexAfterShiftRegion = startIndex + count;
+    unsigned numElementsAfterShiftRegion = usedVectorLength - firstIndexAfterShiftRegion;
+    ASSERT(numElementsBeforeShiftRegion + count + numElementsAfterShiftRegion == usedVectorLength);
+
+    // The point of this comparison seems to be to minimize the amount of elements that have to 
+    // be moved during a shift operation.
+    if (numElementsBeforeShiftRegion < numElementsAfterShiftRegion) {
+        // The number of elements before the shift region is less than the number of elements
+        // after the shift region, so we move the elements before to the right.
+        if (numElementsBeforeShiftRegion) {
+            RELEASE_ASSERT(count + startIndex <= vectorLength);
+            if (storage->hasHoles()) {
+                for (unsigned i = startIndex; i-- > 0;) {
+                    unsigned destinationIndex = count + i;
+                    JSValue source = storage->m_vector[i].get();
+                    JSValue dest = storage->m_vector[destinationIndex].get();
+                    // Any time we overwrite a hole we know we overcounted the number of values we removed 
+                    // when we subtracted count from m_numValuesInVector above.
+                    if (!dest && destinationIndex >= firstIndexAfterShiftRegion)
+                        storage->m_numValuesInVector++;
+                    storage->m_vector[count + i].setWithoutWriteBarrier(source);
+                }
+            } else {
+                memmove(storage->m_vector + count,
+                    storage->m_vector,
+                    sizeof(JSValue) * startIndex);
+            }
+        }
+        // Adjust the Butterfly and the index bias. We only need to do this here because we're changing
+        // the start of the Butterfly, which needs to point at the first indexed property in the used
+        // portion of the vector.
+        m_butterfly.setWithoutWriteBarrier(m_butterfly->shift(structure(), count));
+        storage = m_butterfly->arrayStorage();
+        storage->m_indexBias += count;
+
+        // Since we're consuming part of the vector by moving its beginning to the left,
+        // we need to modify the vector length appropriately.
+        storage->setVectorLength(vectorLength - count);
+    } else {
+        // The number of elements before the shift region is greater than or equal to the number 
+        // of elements after the shift region, so we move the elements after the shift region to the left.
+        if (storage->hasHoles()) {
+            for (unsigned i = 0; i < numElementsAfterShiftRegion; ++i) {
+                unsigned destinationIndex = startIndex + i;
+                JSValue source = storage->m_vector[firstIndexAfterShiftRegion + i].get();
+                JSValue dest = storage->m_vector[destinationIndex].get();
+                // Any time we overwrite a hole we know we overcounted the number of values we removed 
+                // when we subtracted count from m_numValuesInVector above.
+                if (!dest && destinationIndex < firstIndexAfterShiftRegion)
+                    storage->m_numValuesInVector++;
+                storage->m_vector[startIndex + i].setWithoutWriteBarrier(source);

             }
             }

+        } else {
+            memmove(storage->m_vector + startIndex,
+                storage->m_vector + firstIndexAfterShiftRegion,
+                sizeof(JSValue) * numElementsAfterShiftRegion);

         }
         }

+        // Clear the slots of the elements we just moved.
+        unsigned startOfEmptyVectorTail = usedVectorLength - count;
+        for (unsigned i = startOfEmptyVectorTail; i < usedVectorLength; ++i)
+            storage->m_vector[i].clear();
+        // We don't modify the index bias or the Butterfly pointer in this case because we're not changing 
+        // the start of the Butterfly, which needs to point at the first indexed property in the used 
+        // portion of the vector. We also don't modify the vector length because we're not actually changing
+        // its length; we're just using less of it.

     }
     }

-
-    checkConsistency();
-
-    if (i > MAX_ARRAY_INDEX)
-        return deleteProperty(exec, Identifier::from(exec, i));
-
-    return false;
+    
+    return true;

 }
 
 }
 

-void JSArray::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
+bool JSArray::shiftCountWithAnyIndexingType(ExecState* exec, unsigned& startIndex, unsigned count)

 {
 {

-    // 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;
+    VM& vm = exec->vm();
+    RELEASE_ASSERT(count > 0);
+    
+    switch (indexingType()) {
+    case ArrayClass:
+        return true;
+        
+    case ArrayWithUndecided:
+        // Don't handle this because it's confusing and it shouldn't come up.
+        return false;
+        
+    case ArrayWithInt32:
+    case ArrayWithContiguous: {
+        unsigned oldLength = m_butterfly->publicLength();
+        RELEASE_ASSERT(count <= oldLength);
+        
+        // We may have to walk the entire array to do the shift. We're willing to do
+        // so only if it's not horribly slow.
+        if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
+            return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
+
+        // Storing to a hole is fine since we're still having a good time. But reading from a hole 
+        // is totally not fine, since we might have to read from the proto chain.
+        // We have to check for holes before we start moving things around so that we don't get halfway 
+        // through shifting and then realize we should have been in ArrayStorage mode.
+        unsigned end = oldLength - count;
+        if (this->structure(vm)->holesMustForwardToPrototype(vm)) {
+            for (unsigned i = startIndex; i < end; ++i) {
+                JSValue v = m_butterfly->contiguous()[i + count].get();
+                if (UNLIKELY(!v)) {
+                    startIndex = i;
+                    return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
+                }
+                m_butterfly->contiguous()[i].setWithoutWriteBarrier(v);
+            }
+        } else {
+            memmove(m_butterfly->contiguous().data() + startIndex, 
+                m_butterfly->contiguous().data() + startIndex + count, 
+                sizeof(JSValue) * (end - startIndex));
+        }

 
 

-    unsigned usedVectorLength = min(storage->m_length, storage->m_vectorLength);
-    for (unsigned i = 0; i < usedVectorLength; ++i) {
-        if (storage->m_vector[i])
-            propertyNames.add(Identifier::from(exec, i));
+        for (unsigned i = end; i < oldLength; ++i)
+            m_butterfly->contiguous()[i].clear();
+        
+        m_butterfly->setPublicLength(oldLength - count);
+        return true;

     }
     }

-
-    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
-        SparseArrayValueMap::iterator end = map->end();
-        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
-            propertyNames.add(Identifier::from(exec, it->first));
+        
+    case ArrayWithDouble: {
+        unsigned oldLength = m_butterfly->publicLength();
+        RELEASE_ASSERT(count <= oldLength);
+        
+        // We may have to walk the entire array to do the shift. We're willing to do
+        // so only if it's not horribly slow.
+        if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
+            return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
+
+        // Storing to a hole is fine since we're still having a good time. But reading from a hole 
+        // is totally not fine, since we might have to read from the proto chain.
+        // We have to check for holes before we start moving things around so that we don't get halfway 
+        // through shifting and then realize we should have been in ArrayStorage mode.
+        unsigned end = oldLength - count;
+        if (this->structure(vm)->holesMustForwardToPrototype(vm)) {
+            for (unsigned i = startIndex; i < end; ++i) {
+                double v = m_butterfly->contiguousDouble()[i + count];
+                if (UNLIKELY(v != v)) {
+                    startIndex = i;
+                    return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
+                }
+                m_butterfly->contiguousDouble()[i] = v;
+            }
+        } else {
+            memmove(m_butterfly->contiguousDouble().data() + startIndex,
+                m_butterfly->contiguousDouble().data() + startIndex + count,
+                sizeof(JSValue) * (end - startIndex));
+        }
+        for (unsigned i = end; i < oldLength; ++i)
+            m_butterfly->contiguousDouble()[i] = PNaN;
+        
+        m_butterfly->setPublicLength(oldLength - count);
+        return true;
+    }
+        
+    case ArrayWithArrayStorage:
+    case ArrayWithSlowPutArrayStorage:
+        return shiftCountWithArrayStorage(vm, startIndex, count, arrayStorage());
+        
+    default:
+        CRASH();
+        return false;

     }
     }

-
-    JSObject::getPropertyNames(exec, propertyNames);

 }
 
 }
 

-bool JSArray::increaseVectorLength(unsigned newLength)
+// Returns true if the unshift can be handled, false to fallback.    
+bool JSArray::unshiftCountWithArrayStorage(ExecState* exec, unsigned startIndex, unsigned count, ArrayStorage* storage)

 {
 {

-    // 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 length = storage->length();

 
 

-    unsigned vectorLength = storage->m_vectorLength;
-    ASSERT(newLength > vectorLength);
-    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
-    unsigned newVectorLength = increasedVectorLength(newLength);
+    RELEASE_ASSERT(startIndex <= length);

 
 

-    storage = static_cast<ArrayStorage*>(tryFastRealloc(storage, storageSize(newVectorLength)));
-    if (!storage)
+    // If the array contains holes or is otherwise in an abnormal state,
+    // use the generic algorithm in ArrayPrototype.
+    if (storage->hasHoles() || storage->inSparseMode() || shouldUseSlowPut(indexingType()))

         return false;
 
         return false;
 

-    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
-    storage->m_vectorLength = newVectorLength;
+    bool moveFront = !startIndex || startIndex < length / 2;
+
+    unsigned vectorLength = storage->vectorLength();
+
+    if (moveFront && storage->m_indexBias >= count) {
+        Butterfly* newButterfly = storage->butterfly()->unshift(structure(), count);
+        storage = newButterfly->arrayStorage();
+        storage->m_indexBias -= count;
+        storage->setVectorLength(vectorLength + count);
+        setButterflyWithoutChangingStructure(exec->vm(), newButterfly);
+    } else if (!moveFront && vectorLength - length >= count)
+        storage = storage->butterfly()->arrayStorage();
+    else if (unshiftCountSlowCase(exec->vm(), moveFront, count))
+        storage = arrayStorage();
+    else {
+        throwOutOfMemoryError(exec);
+        return true;
+    }
+
+    WriteBarrier<Unknown>* vector = storage->m_vector;

 
 

-    for (unsigned i = vectorLength; i < newVectorLength; ++i)
-        storage->m_vector[i] = JSValue();
+    if (startIndex) {
+        if (moveFront)
+            memmove(vector, vector + count, startIndex * sizeof(JSValue));
+        else if (length - startIndex)
+            memmove(vector + startIndex + count, vector + startIndex, (length - startIndex) * sizeof(JSValue));
+    }

 
 

-    m_storage = storage;
+    for (unsigned i = 0; i < count; i++)
+        vector[i + startIndex].clear();

     return true;
 }
 
     return true;
 }
 

-void JSArray::setLength(unsigned newLength)
+bool JSArray::unshiftCountWithAnyIndexingType(ExecState* exec, unsigned startIndex, unsigned count)

 {
 {

-    checkConsistency();
-
-    ArrayStorage* storage = m_storage;
-
-    unsigned length = m_storage->m_length;
-
-    if (newLength < length) {
-        if (m_fastAccessCutoff > newLength)
-            m_fastAccessCutoff = newLength;
+    switch (indexingType()) {
+    case ArrayClass:
+    case ArrayWithUndecided:
+        // We could handle this. But it shouldn't ever come up, so we won't.
+        return false;

 
 

-        unsigned usedVectorLength = min(length, storage->m_vectorLength);
-        for (unsigned i = newLength; i < usedVectorLength; ++i) {
-            JSValue& valueSlot = storage->m_vector[i];
-            bool hadValue = valueSlot;
-            valueSlot = JSValue();
-            storage->m_numValuesInVector -= hadValue;
+    case ArrayWithInt32:
+    case ArrayWithContiguous: {
+        unsigned oldLength = m_butterfly->publicLength();
+        
+        // We may have to walk the entire array to do the unshift. We're willing to do so
+        // only if it's not horribly slow.
+        if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
+            return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
+        
+        ensureLength(exec->vm(), oldLength + count);
+
+        // We have to check for holes before we start moving things around so that we don't get halfway 
+        // through shifting and then realize we should have been in ArrayStorage mode.
+        for (unsigned i = oldLength; i-- > startIndex;) {
+            JSValue v = m_butterfly->contiguous()[i].get();
+            if (UNLIKELY(!v))
+                return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));

         }
 
         }
 

-        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
-            SparseArrayValueMap copy = *map;
-            SparseArrayValueMap::iterator end = copy.end();
-            for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
-                if (it->first >= newLength)
-                    map->remove(it->first);
-            }
-            if (map->isEmpty()) {
-                delete map;
-                storage->m_sparseValueMap = 0;
-            }
+        for (unsigned i = oldLength; i-- > startIndex;) {
+            JSValue v = m_butterfly->contiguous()[i].get();
+            ASSERT(v);
+            m_butterfly->contiguous()[i + count].setWithoutWriteBarrier(v);

         }
         }

+        
+        // NOTE: we're leaving being garbage in the part of the array that we shifted out
+        // of. This is fine because the caller is required to store over that area, and
+        // in contiguous mode storing into a hole is guaranteed to behave exactly the same
+        // as storing over an existing element.
+        
+        return true;

     }
     }

+        
+    case ArrayWithDouble: {
+        unsigned oldLength = m_butterfly->publicLength();
+        
+        // We may have to walk the entire array to do the unshift. We're willing to do so
+        // only if it's not horribly slow.
+        if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
+            return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
+        
+        ensureLength(exec->vm(), oldLength + count);
+        
+        // We have to check for holes before we start moving things around so that we don't get halfway 
+        // through shifting and then realize we should have been in ArrayStorage mode.
+        for (unsigned i = oldLength; i-- > startIndex;) {
+            double v = m_butterfly->contiguousDouble()[i];
+            if (UNLIKELY(v != v))
+                return unshiftCountWithArrayStorage(exec, startIndex, count, ensureArrayStorage(exec->vm()));
+        }

 
 

-    m_storage->m_length = newLength;
-
-    checkConsistency();
-}
-
-JSValue JSArray::pop()
-{
-    checkConsistency();
-
-    unsigned length = m_storage->m_length;
-    if (!length)
-        return jsUndefined();
-
-    --length;
-
-    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
-            result = jsUndefined();
-    } else {
-        result = jsUndefined();
-        if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
-            SparseArrayValueMap::iterator it = map->find(length);
-            if (it != map->end()) {
-                result = it->second;
-                map->remove(it);
-                if (map->isEmpty()) {
-                    delete map;
-                    m_storage->m_sparseValueMap = 0;
-                }
-            }
+        for (unsigned i = oldLength; i-- > startIndex;) {
+            double v = m_butterfly->contiguousDouble()[i];
+            ASSERT(v == v);
+            m_butterfly->contiguousDouble()[i + count] = v;

         }
         }

+        
+        // NOTE: we're leaving being garbage in the part of the array that we shifted out
+        // of. This is fine because the caller is required to store over that area, and
+        // in contiguous mode storing into a hole is guaranteed to behave exactly the same
+        // as storing over an existing element.
+        
+        return true;
+    }
+        
+    case ArrayWithArrayStorage:
+    case ArrayWithSlowPutArrayStorage:
+        return unshiftCountWithArrayStorage(exec, startIndex, count, arrayStorage());
+        
+    default:
+        CRASH();
+        return false;

     }
     }

-
-    m_storage->m_length = length;
-
-    checkConsistency();
-
-    return result;

 }
 
 }
 

-void JSArray::push(ExecState* exec, JSValue value)
+static int compareNumbersForQSortWithInt32(const void* a, const void* b)

 {
 {

-    checkConsistency();
-
-    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;
-        checkConsistency();
-        return;
-    }
-
-    if (m_storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
-        SparseArrayValueMap* map = m_storage->m_sparseValueMap;
-        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;
-                checkConsistency();
-                return;
-            }
-            checkConsistency();
-            throwOutOfMemoryError(exec);
-            return;
-        }
-    }
-
-    putSlowCase(exec, m_storage->m_length++, value);
+    int32_t ia = static_cast<const JSValue*>(a)->asInt32();
+    int32_t ib = static_cast<const JSValue*>(b)->asInt32();
+    return ia - ib;

 }
 
 }
 

-void JSArray::mark()
+static int compareNumbersForQSortWithDouble(const void* a, const void* b)

 {
 {

-    JSObject::mark();
-
-    ArrayStorage* storage = m_storage;
-
-    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();
-    }
-
-    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();
-        }
-    }
+    double da = *static_cast<const double*>(a);
+    double db = *static_cast<const double*>(b);
+    return (da > db) - (da < db);

 }
 
 static int compareNumbersForQSort(const void* a, const void* b)
 {
 }
 
 static int compareNumbersForQSort(const void* a, const void* b)
 {

-    double da = static_cast<const JSValue*>(a)->uncheckedGetNumber();
-    double db = static_cast<const JSValue*>(b)->uncheckedGetNumber();
+    double da = static_cast<const JSValue*>(a)->asNumber();
+    double db = static_cast<const JSValue*>(b)->asNumber();

     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)
+template<IndexingType arrayIndexingType>
+void JSArray::sortNumericVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)

 {
 {

-    unsigned lengthNotIncludingUndefined = compactForSorting();
-    if (m_storage->m_sparseValueMap) {
+    ASSERT(arrayIndexingType == ArrayWithInt32 || arrayIndexingType == ArrayWithDouble || arrayIndexingType == ArrayWithContiguous || arrayIndexingType == ArrayWithArrayStorage);
+    
+    unsigned lengthNotIncludingUndefined;
+    unsigned newRelevantLength;
+    compactForSorting<arrayIndexingType>(
+        lengthNotIncludingUndefined,
+        newRelevantLength);
+    
+    ContiguousJSValues data = indexingData<arrayIndexingType>();
+    
+    if (arrayIndexingType == ArrayWithArrayStorage && arrayStorage()->m_sparseMap.get()) {

         throwOutOfMemoryError(exec);
         return;
     }
         throwOutOfMemoryError(exec);
         return;
     }

-
+    

     if (!lengthNotIncludingUndefined)
         return;
     if (!lengthNotIncludingUndefined)
         return;

-        
+    

     bool allValuesAreNumbers = true;
     bool allValuesAreNumbers = true;

-    size_t size = m_storage->m_numValuesInVector;
-    for (size_t i = 0; i < size; ++i) {
-        if (!m_storage->m_vector[i].isNumber()) {
-            allValuesAreNumbers = false;
-            break;
+    switch (arrayIndexingType) {
+    case ArrayWithInt32:
+    case ArrayWithDouble:
+        break;
+        
+    default:
+        for (size_t i = 0; i < newRelevantLength; ++i) {
+            if (!data[i].isNumber()) {
+                allValuesAreNumbers = false;
+                break;
+            }

         }
         }

+        break;

     }
     }

-
+    

     if (!allValuesAreNumbers)
         return sort(exec, compareFunction, callType, callData);
     if (!allValuesAreNumbers)
         return sort(exec, compareFunction, callType, callData);

-
+    

     // 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);
-
-    checkConsistency(SortConsistencyCheck);
+    int (*compare)(const void*, const void*);
+    switch (arrayIndexingType) {
+    case ArrayWithInt32:
+        compare = compareNumbersForQSortWithInt32;
+        break;
+        
+    case ArrayWithDouble:
+        compare = compareNumbersForQSortWithDouble;
+        ASSERT(sizeof(WriteBarrier<Unknown>) == sizeof(double));
+        break;
+        
+    default:
+        compare = compareNumbersForQSort;
+        break;
+    }
+    ASSERT(data.length() >= newRelevantLength);
+    qsort(data.data(), newRelevantLength, sizeof(WriteBarrier<Unknown>), compare);
+    return;

 }
 
 }
 

-void JSArray::sort(ExecState* exec)
+void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)

 {
 {

-    unsigned lengthNotIncludingUndefined = compactForSorting();
-    if (m_storage->m_sparseValueMap) {
-        throwOutOfMemoryError(exec);
+    ASSERT(!inSparseIndexingMode());
+
+    switch (indexingType()) {
+    case ArrayClass:
+        return;
+        
+    case ArrayWithInt32:
+        sortNumericVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
+        break;
+        
+    case ArrayWithDouble:
+        sortNumericVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
+        break;
+        
+    case ArrayWithContiguous:
+        sortNumericVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
+        return;
+
+    case ArrayWithArrayStorage:
+        sortNumericVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
+        return;
+        
+    default:
+        CRASH();

         return;
     }
         return;
     }

+}

 
 

-    if (!lengthNotIncludingUndefined)
+template <IndexingType> struct ContiguousTypeAccessor {
+    typedef WriteBarrier<Unknown> Type;
+    static JSValue getAsValue(ContiguousData<Type> data, size_t i) { return data[i].get(); }
+    static void setWithValue(VM& vm, JSArray* thisValue, ContiguousData<Type> data, size_t i, JSValue value)
+    {
+        data[i].set(vm, thisValue, value);
+    }
+    static void replaceDataReference(ContiguousData<Type>* outData, ContiguousJSValues inData)
+    {
+        *outData = inData;
+    }
+};
+
+template <> struct ContiguousTypeAccessor<ArrayWithDouble> {
+    typedef double Type;
+    static JSValue getAsValue(ContiguousData<Type> data, size_t i) { ASSERT(data[i] == data[i]); return JSValue(JSValue::EncodeAsDouble, data[i]); }
+    static void setWithValue(VM&, JSArray*, ContiguousData<Type> data, size_t i, JSValue value)
+    {
+        data[i] = value.asNumber();
+    }
+    static NO_RETURN_DUE_TO_CRASH void replaceDataReference(ContiguousData<Type>*, ContiguousJSValues)
+    {
+        RELEASE_ASSERT_WITH_MESSAGE(0, "Inconsistent indexing types during compact array sort.");
+    }
+};
+
+
+template<IndexingType arrayIndexingType, typename StorageType>
+void JSArray::sortCompactedVector(ExecState* exec, ContiguousData<StorageType> data, unsigned relevantLength)
+{
+    if (!relevantLength)

         return;
         return;

+    
+    VM& vm = exec->vm();

 
     // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
     // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
     // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
     // random or otherwise changing results, effectively making compare function inconsistent.
 
     // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
     // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
     // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
     // random or otherwise changing results, effectively making compare function inconsistent.

-
-    Vector<ValueStringPair> values(lengthNotIncludingUndefined);
+        
+    Vector<ValueStringPair, 0, UnsafeVectorOverflow> values(relevantLength);

     if (!values.begin()) {
         throwOutOfMemoryError(exec);
         return;
     }
     if (!values.begin()) {
         throwOutOfMemoryError(exec);
         return;
     }

+        
+    Heap::heap(this)->pushTempSortVector(&values);
+        
+    bool isSortingPrimitiveValues = true;

 
 

-    for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
-        JSValue value = m_storage->m_vector[i];
+    for (size_t i = 0; i < relevantLength; i++) {
+        JSValue value = ContiguousTypeAccessor<arrayIndexingType>::getAsValue(data, i);
+        ASSERT(arrayIndexingType != ArrayWithInt32 || value.isInt32());

         ASSERT(!value.isUndefined());
         values[i].first = value;
         ASSERT(!value.isUndefined());
         values[i].first = value;

+        if (arrayIndexingType != ArrayWithDouble && arrayIndexingType != ArrayWithInt32)
+            isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive();

     }
     }

-
-    // 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.
     // 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())
+        
+    for (size_t i = 0; i < relevantLength; i++)
+        values[i].second = values[i].first.toWTFStringInline(exec);
+        
+    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).

-
+        

 #if HAVE(MERGESORT)
 #if HAVE(MERGESORT)

-    mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+    if (isSortingPrimitiveValues)
+        qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+    else
+        mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);

 #else
     // FIXME: The qsort library function is likely to not be a stable sort.
     // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
     qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 #endif
 #else
     // FIXME: The qsort library function is likely to not be a stable sort.
     // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
     qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 #endif

+    
+    // If the toString function changed the length of the array or vector storage,
+    // increase the length to handle the orignal number of actual values.
+    switch (arrayIndexingType) {
+    case ArrayWithInt32:
+    case ArrayWithDouble:
+    case ArrayWithContiguous:
+        ensureLength(vm, relevantLength);
+        break;
+        
+    case ArrayWithArrayStorage:
+        if (arrayStorage()->vectorLength() < relevantLength) {
+            increaseVectorLength(exec->vm(), relevantLength);
+            ContiguousTypeAccessor<arrayIndexingType>::replaceDataReference(&data, arrayStorage()->vector());
+        }
+        if (arrayStorage()->length() < relevantLength)
+            arrayStorage()->setLength(relevantLength);
+        break;
+        
+    default:
+        CRASH();
+    }

 
 

-    // FIXME: If the toString function changed the length of the array, this might be
-    // modifying the vector incorrectly.
-
-    for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
-        m_storage->m_vector[i] = values[i].first;
+    for (size_t i = 0; i < relevantLength; i++)
+        ContiguousTypeAccessor<arrayIndexingType>::setWithValue(vm, this, data, i, values[i].first);
+    
+    Heap::heap(this)->popTempSortVector(&values);
+}

 
 

-    checkConsistency(SortConsistencyCheck);
+void JSArray::sort(ExecState* exec)
+{
+    ASSERT(!inSparseIndexingMode());
+    
+    switch (indexingType()) {
+    case ArrayClass:
+    case ArrayWithUndecided:
+        return;
+        
+    case ArrayWithInt32: {
+        unsigned lengthNotIncludingUndefined;
+        unsigned newRelevantLength;
+        compactForSorting<ArrayWithInt32>(
+            lengthNotIncludingUndefined, newRelevantLength);
+        
+        sortCompactedVector<ArrayWithInt32>(
+            exec, m_butterfly->contiguousInt32(), lengthNotIncludingUndefined);
+        return;
+    }
+        
+    case ArrayWithDouble: {
+        unsigned lengthNotIncludingUndefined;
+        unsigned newRelevantLength;
+        compactForSorting<ArrayWithDouble>(
+            lengthNotIncludingUndefined, newRelevantLength);
+        
+        sortCompactedVector<ArrayWithDouble>(
+            exec, m_butterfly->contiguousDouble(), lengthNotIncludingUndefined);
+        return;
+    }
+        
+    case ArrayWithContiguous: {
+        unsigned lengthNotIncludingUndefined;
+        unsigned newRelevantLength;
+        compactForSorting<ArrayWithContiguous>(
+            lengthNotIncludingUndefined, newRelevantLength);
+        
+        sortCompactedVector<ArrayWithContiguous>(
+            exec, m_butterfly->contiguous(), lengthNotIncludingUndefined);
+        return;
+    }
+        
+    case ArrayWithArrayStorage: {
+        unsigned lengthNotIncludingUndefined;
+        unsigned newRelevantLength;
+        compactForSorting<ArrayWithArrayStorage>(
+            lengthNotIncludingUndefined, newRelevantLength);
+        ArrayStorage* storage = m_butterfly->arrayStorage();
+        ASSERT(!storage->m_sparseMap);
+        
+        sortCompactedVector<ArrayWithArrayStorage>(exec, storage->vector(), lengthNotIncludingUndefined);
+        return;
+    }
+        
+    default:
+        RELEASE_ASSERT_NOT_REACHED();
+    }

 }
 
 struct AVLTreeNodeForArrayCompare {
 }
 
 struct AVLTreeNodeForArrayCompare {


@@ -746,12 +1302,11 @@ struct AVLTreeAbstractorForArrayCompare {
     typedef JSValue key;
     typedef int32_t size;
 
     typedef JSValue key;
     typedef int32_t size;
 

-    Vector<AVLTreeNodeForArrayCompare> m_nodes;
+    Vector<AVLTreeNodeForArrayCompare, 0, UnsafeVectorOverflow> m_nodes;

     ExecState* m_exec;
     JSValue m_compareFunction;
     CallType m_compareCallType;
     const CallData* m_compareCallData;
     ExecState* m_exec;
     JSValue m_compareFunction;
     CallType m_compareCallType;
     const CallData* m_compareCallData;

-    JSValue m_globalThisValue;

     OwnPtr<CachedCall> m_cachedCall;
 
     handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
     OwnPtr<CachedCall> m_cachedCall;
 
     handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }


@@ -790,15 +1345,15 @@ struct AVLTreeAbstractorForArrayCompare {
 
         double compareResult;
         if (m_cachedCall) {
 
         double compareResult;
         if (m_cachedCall) {

-            m_cachedCall->setThis(m_globalThisValue);
+            m_cachedCall->setThis(jsUndefined());

             m_cachedCall->setArgument(0, va);
             m_cachedCall->setArgument(1, vb);
             m_cachedCall->setArgument(0, va);
             m_cachedCall->setArgument(1, vb);

-            compareResult = m_cachedCall->call().toNumber(m_cachedCall->newCallFrame());
+            compareResult = m_cachedCall->call().toNumber(m_exec);

         } else {
             MarkedArgumentBuffer arguments;
             arguments.append(va);
             arguments.append(vb);
         } else {
             MarkedArgumentBuffer arguments;
             arguments.append(va);
             arguments.append(vb);

-            compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, m_globalThisValue, arguments).toNumber(m_exec);
+            compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, jsUndefined(), arguments).toNumber(m_exec);

         }
         return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
     }
         }
         return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
     }


@@ -809,55 +1364,61 @@ struct AVLTreeAbstractorForArrayCompare {
     static handle null() { return 0x7FFFFFFF; }
 };
 
     static handle null() { return 0x7FFFFFFF; }
 };
 

-void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
+template<IndexingType arrayIndexingType>
+void JSArray::sortVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)

 {
 {

-    checkConsistency();
-
+    ASSERT(!inSparseIndexingMode());
+    ASSERT(arrayIndexingType == indexingType());
+    

     // FIXME: This ignores exceptions raised in the compare function or in toNumber.
     // 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.
     // 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(m_butterfly->publicLength() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
+    if (m_butterfly->publicLength() > static_cast<unsigned>(std::numeric_limits<int>::max()))

         return;
         return;

-
-    if (!m_storage->m_length)
+        
+    unsigned usedVectorLength = relevantLength<arrayIndexingType>();
+    unsigned nodeCount = usedVectorLength;
+        
+    if (!nodeCount)

         return;
         return;

-
-    unsigned usedVectorLength = min(m_storage->m_length, m_storage->m_vectorLength);
-
+        

     AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
     tree.abstractor().m_exec = exec;
     tree.abstractor().m_compareFunction = compareFunction;
     tree.abstractor().m_compareCallType = callType;
     tree.abstractor().m_compareCallData = &callData;
     AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
     tree.abstractor().m_exec = exec;
     tree.abstractor().m_compareFunction = compareFunction;
     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, jsCast<JSFunction*>(compareFunction), 2));
+        

     if (!tree.abstractor().m_nodes.begin()) {
         throwOutOfMemoryError(exec);
         return;
     }
     if (!tree.abstractor().m_nodes.begin()) {
         throwOutOfMemoryError(exec);
         return;
     }

-
+        

     // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
     // right out from under us while we're building the tree here.
     // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
     // right out from under us while we're building the tree here.

-
+        

     unsigned numDefined = 0;
     unsigned numUndefined = 0;
     unsigned numDefined = 0;
     unsigned numUndefined = 0;

-
+    

     // 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];
+        if (numDefined >= m_butterfly->vectorLength())
+            break;
+        JSValue v = getHolyIndexQuickly(numDefined);

         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];
+        if (i >= m_butterfly->vectorLength())
+            break;
+        JSValue v = getHolyIndexQuickly(i);

         if (v) {
             if (v.isUndefined())
                 ++numUndefined;
         if (v) {
             if (v.isUndefined())
                 ++numUndefined;


@@ -868,211 +1429,297 @@ void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType,
             }
         }
     }
             }
         }
     }

-
+    

     unsigned newUsedVectorLength = numDefined + numUndefined;
     unsigned newUsedVectorLength = numDefined + numUndefined;

-
-    if (SparseArrayValueMap* map = m_storage->m_sparseValueMap) {
-        newUsedVectorLength += map->size();
-        if (newUsedVectorLength > m_storage->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;
-            }
-        }
-
-        SparseArrayValueMap::iterator end = map->end();
-        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
-            tree.abstractor().m_nodes[numDefined].value = it->second;
-            tree.insert(numDefined);
-            ++numDefined;
-        }
-
-        delete map;
-        m_storage->m_sparseValueMap = 0;
-    }
-
-    ASSERT(tree.abstractor().m_nodes.size() >= numDefined);
-
-    // FIXME: If the compare function changed the length of the array, the following might be
-    // modifying the vector incorrectly.
-
+        
+    // The array size may have changed. Figure out the new bounds.
+    unsigned newestUsedVectorLength = currentRelevantLength();
+        
+    unsigned elementsToExtractThreshold = min(min(newestUsedVectorLength, numDefined), static_cast<unsigned>(tree.abstractor().m_nodes.size()));
+    unsigned undefinedElementsThreshold = min(newestUsedVectorLength, newUsedVectorLength);
+    unsigned clearElementsThreshold = min(newestUsedVectorLength, usedVectorLength);
+        

     // 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);

-    for (unsigned i = 0; i < numDefined; ++i) {
-        m_storage->m_vector[i] = tree.abstractor().m_nodes[*iter].value;
+    VM& vm = exec->vm();
+    for (unsigned i = 0; i < elementsToExtractThreshold; ++i) {
+        ASSERT(i < butterfly()->vectorLength());
+        if (indexingType() == ArrayWithDouble)
+            butterfly()->contiguousDouble()[i] = tree.abstractor().m_nodes[*iter].value.asNumber();
+        else
+            currentIndexingData()[i].set(vm, this, tree.abstractor().m_nodes[*iter].value);

         ++iter;
     }
         ++iter;
     }

-

     // Put undefined values back in.
     // Put undefined values back in.

-    for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
-        m_storage->m_vector[i] = jsUndefined();
+    switch (indexingType()) {
+    case ArrayWithInt32:
+    case ArrayWithDouble:
+        ASSERT(elementsToExtractThreshold == undefinedElementsThreshold);
+        break;
+        
+    default:
+        for (unsigned i = elementsToExtractThreshold; i < undefinedElementsThreshold; ++i) {
+            ASSERT(i < butterfly()->vectorLength());
+            currentIndexingData()[i].setUndefined();
+        }
+    }

 
     // Ensure that unused values in the vector are zeroed out.
 
     // Ensure that unused values in the vector are zeroed out.

-    for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
-        m_storage->m_vector[i] = JSValue();
+    for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i) {
+        ASSERT(i < butterfly()->vectorLength());
+        if (indexingType() == ArrayWithDouble)
+            butterfly()->contiguousDouble()[i] = PNaN;
+        else
+            currentIndexingData()[i].clear();
+    }
+    
+    if (hasAnyArrayStorage(indexingType()))
+        arrayStorage()->m_numValuesInVector = newUsedVectorLength;
+}

 
 

-    m_fastAccessCutoff = newUsedVectorLength;
-    m_storage->m_numValuesInVector = newUsedVectorLength;
+void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
+{
+    ASSERT(!inSparseIndexingMode());
+    
+    switch (indexingType()) {
+    case ArrayClass:
+    case ArrayWithUndecided:
+        return;
+        
+    case ArrayWithInt32:
+        sortVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
+        return;

 
 

-    checkConsistency(SortConsistencyCheck);
+    case ArrayWithDouble:
+        sortVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
+        return;
+
+    case ArrayWithContiguous:
+        sortVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
+        return;
+
+    case ArrayWithArrayStorage:
+        sortVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
+        return;
+        
+    default:
+        RELEASE_ASSERT_NOT_REACHED();
+    }

 }
 
 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
 {
 }
 
 void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
 {

-    unsigned fastAccessLength = min(m_storage->m_length, m_fastAccessCutoff);

     unsigned i = 0;
     unsigned i = 0;

-    for (; i < fastAccessLength; ++i)
-        args.append(getIndex(i));
-    for (; i < m_storage->m_length; ++i)
+    unsigned vectorEnd;
+    WriteBarrier<Unknown>* vector;
+    
+    switch (indexingType()) {
+    case ArrayClass:
+        return;
+        
+    case ArrayWithUndecided: {
+        vector = 0;
+        vectorEnd = 0;
+        break;
+    }
+        
+    case ArrayWithInt32:
+    case ArrayWithContiguous: {
+        vectorEnd = m_butterfly->publicLength();
+        vector = m_butterfly->contiguous().data();
+        break;
+    }
+        
+    case ArrayWithDouble: {
+        vector = 0;
+        vectorEnd = 0;
+        for (; i < m_butterfly->publicLength(); ++i) {
+            double v = butterfly()->contiguousDouble()[i];
+            if (v != v)
+                break;
+            args.append(JSValue(JSValue::EncodeAsDouble, v));
+        }
+        break;
+    }
+    
+    case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
+        ArrayStorage* storage = m_butterfly->arrayStorage();
+        
+        vector = storage->m_vector;
+        vectorEnd = min(storage->length(), storage->vectorLength());
+        break;
+    }
+        
+    default:
+        CRASH();
+        vector = 0;
+        vectorEnd = 0;
+        break;
+    }
+    
+    for (; i < vectorEnd; ++i) {
+        WriteBarrier<Unknown>& v = vector[i];
+        if (!v)
+            break;
+        args.append(v.get());
+    }
+    
+    for (; i < length(); ++i)

         args.append(get(exec, i));
 }
 
         args.append(get(exec, i));
 }
 

-void JSArray::copyToRegisters(ExecState* exec, Register* buffer, uint32_t maxSize)
+void JSArray::copyToArguments(ExecState* exec, CallFrame* callFrame, uint32_t copyLength, int32_t firstVarArgOffset)

 {
 {

-    ASSERT(m_storage->m_length == maxSize);
-    UNUSED_PARAM(maxSize);
-    unsigned fastAccessLength = min(m_storage->m_length, m_fastAccessCutoff);
-    unsigned i = 0;
-    for (; i < fastAccessLength; ++i)
-        buffer[i] = getIndex(i);
-    uint32_t size = m_storage->m_length;
-    for (; i < size; ++i)
-        buffer[i] = get(exec, i);
+    unsigned i = firstVarArgOffset;
+    WriteBarrier<Unknown>* vector;
+    unsigned vectorEnd;
+    unsigned length = copyLength + firstVarArgOffset;
+    ASSERT(length == this->length());
+    switch (indexingType()) {
+    case ArrayClass:
+        return;
+        
+    case ArrayWithUndecided: {
+        vector = 0;
+        vectorEnd = 0;
+        break;
+    }
+        
+    case ArrayWithInt32:
+    case ArrayWithContiguous: {
+        vector = m_butterfly->contiguous().data();
+        vectorEnd = m_butterfly->publicLength();
+        break;
+    }
+        
+    case ArrayWithDouble: {
+        vector = 0;
+        vectorEnd = 0;
+        for (; i < m_butterfly->publicLength(); ++i) {
+            ASSERT(i < butterfly()->vectorLength());
+            double v = m_butterfly->contiguousDouble()[i];
+            if (v != v)
+                break;
+            callFrame->setArgument(i - firstVarArgOffset, JSValue(JSValue::EncodeAsDouble, v));
+        }
+        break;
+    }
+        
+    case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
+        ArrayStorage* storage = m_butterfly->arrayStorage();
+        vector = storage->m_vector;
+        vectorEnd = min(length, storage->vectorLength());
+        break;
+    }
+        
+    default:
+        CRASH();
+        vector = 0;
+        vectorEnd = 0;
+        break;
+    }
+    
+    for (; i < vectorEnd; ++i) {
+        WriteBarrier<Unknown>& v = vector[i];
+        if (!v)
+            break;
+        callFrame->setArgument(i - firstVarArgOffset, v.get());
+    }
+    
+    for (; i < length; ++i)
+        callFrame->setArgument(i - firstVarArgOffset, get(exec, i));

 }
 
 }
 

-unsigned JSArray::compactForSorting()
+template<IndexingType arrayIndexingType>
+void JSArray::compactForSorting(unsigned& numDefined, unsigned& newRelevantLength)

 {
 {

-    checkConsistency();
-
-    ArrayStorage* storage = m_storage;
+    ASSERT(!inSparseIndexingMode());
+    ASSERT(arrayIndexingType == indexingType());

 
 

-    unsigned usedVectorLength = min(m_storage->m_length, storage->m_vectorLength);
-
-    unsigned numDefined = 0;
+    unsigned myRelevantLength = relevantLength<arrayIndexingType>();
+    
+    numDefined = 0;

     unsigned numUndefined = 0;
     unsigned numUndefined = 0;

-
-    for (; numDefined < usedVectorLength; ++numDefined) {
-        JSValue v = storage->m_vector[numDefined];
+        
+    for (; numDefined < myRelevantLength; ++numDefined) {
+        ASSERT(numDefined < m_butterfly->vectorLength());
+        if (arrayIndexingType == ArrayWithInt32) {
+            JSValue v = m_butterfly->contiguousInt32()[numDefined].get();
+            if (!v)
+                break;
+            ASSERT(v.isInt32());
+            continue;
+        }
+        if (arrayIndexingType == ArrayWithDouble) {
+            double v = m_butterfly->contiguousDouble()[numDefined];
+            if (v != v)
+                break;
+            continue;
+        }
+        JSValue v = indexingData<arrayIndexingType>()[numDefined].get();

         if (!v || v.isUndefined())
             break;
     }
         if (!v || v.isUndefined())
             break;
     }

-    for (unsigned i = numDefined; i < usedVectorLength; ++i) {
-        JSValue v = storage->m_vector[i];
+        
+    for (unsigned i = numDefined; i < myRelevantLength; ++i) {
+        ASSERT(i < m_butterfly->vectorLength());
+        if (arrayIndexingType == ArrayWithInt32) {
+            JSValue v = m_butterfly->contiguousInt32()[i].get();
+            if (!v)
+                continue;
+            ASSERT(v.isInt32());
+            ASSERT(numDefined < m_butterfly->vectorLength());
+            m_butterfly->contiguousInt32()[numDefined++].setWithoutWriteBarrier(v);
+            continue;
+        }
+        if (arrayIndexingType == ArrayWithDouble) {
+            double v = m_butterfly->contiguousDouble()[i];
+            if (v != v)
+                continue;
+            ASSERT(numDefined < m_butterfly->vectorLength());
+            m_butterfly->contiguousDouble()[numDefined++] = v;
+            continue;
+        }
+        JSValue v = indexingData<arrayIndexingType>()[i].get();

         if (v) {
             if (v.isUndefined())
                 ++numUndefined;
         if (v) {
             if (v.isUndefined())
                 ++numUndefined;

-            else
-                storage->m_vector[numDefined++] = v;
-        }
-    }
-
-    unsigned newUsedVectorLength = numDefined + numUndefined;
-
-    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
-        newUsedVectorLength += map->size();
-        if (newUsedVectorLength > storage->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;
-            storage = m_storage;
+            else {
+                ASSERT(numDefined < m_butterfly->vectorLength());
+                indexingData<arrayIndexingType>()[numDefined++].setWithoutWriteBarrier(v);
+            }

         }
         }

-
-        SparseArrayValueMap::iterator end = map->end();
-        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
-            storage->m_vector[numDefined++] = it->second;
-
-        delete map;
-        storage->m_sparseValueMap = 0;

     }
     }

-
-    for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
-        storage->m_vector[i] = jsUndefined();
-    for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
-        storage->m_vector[i] = JSValue();
-
-    m_fastAccessCutoff = newUsedVectorLength;
-    storage->m_numValuesInVector = newUsedVectorLength;
-
-    checkConsistency(SortConsistencyCheck);
-
-    return numDefined;
-}
-
-void* JSArray::lazyCreationData()
-{
-    return m_storage->lazyCreationData;
-}
-
-void JSArray::setLazyCreationData(void* d)
-{
-    m_storage->lazyCreationData = d;
-}
-
-#if CHECK_ARRAY_CONSISTENCY
-
-void JSArray::checkConsistency(ConsistencyCheckType type)
-{
-    ASSERT(m_storage);
-    if (type == SortConsistencyCheck)
-        ASSERT(!m_storage->m_sparseValueMap);
-
-    ASSERT(m_fastAccessCutoff <= m_storage->m_length);
-    ASSERT(m_fastAccessCutoff <= m_storage->m_numValuesInVector);
-
-    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);
-            if (type != DestructorConsistencyCheck)
-                value->type(); // Likely to crash if the object was deallocated.
-            ++numValuesInVector;
-        } else {
-            ASSERT(i >= m_fastAccessCutoff);
-            if (type == SortConsistencyCheck)
-                ASSERT(i >= m_storage->m_numValuesInVector);
+        
+    newRelevantLength = numDefined + numUndefined;
+    
+    if (hasAnyArrayStorage(arrayIndexingType))
+        RELEASE_ASSERT(!arrayStorage()->m_sparseMap);
+    
+    switch (arrayIndexingType) {
+    case ArrayWithInt32:
+    case ArrayWithDouble:
+        RELEASE_ASSERT(numDefined == newRelevantLength);
+        break;
+        
+    default:
+        for (unsigned i = numDefined; i < newRelevantLength; ++i) {
+            ASSERT(i < m_butterfly->vectorLength());
+            indexingData<arrayIndexingType>()[i].setUndefined();

         }
         }

+        break;

     }
     }

-    ASSERT(numValuesInVector == m_storage->m_numValuesInVector);
-
-    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) {
-            unsigned index = it->first;
-            ASSERT(index < m_storage->m_length);
-            ASSERT(index >= m_storage->m_vectorLength);
-            ASSERT(index <= MAX_ARRAY_INDEX);
-            ASSERT(it->second);
-            if (type != DestructorConsistencyCheck)
-                it->second->type(); // Likely to crash if the object was deallocated.
-        }
+    for (unsigned i = newRelevantLength; i < myRelevantLength; ++i) {
+        ASSERT(i < m_butterfly->vectorLength());
+        if (arrayIndexingType == ArrayWithDouble)
+            m_butterfly->contiguousDouble()[i] = PNaN;
+        else
+            indexingData<arrayIndexingType>()[i].clear();

     }
     }

-}
-
-#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);
+    if (hasAnyArrayStorage(arrayIndexingType))
+        arrayStorage()->m_numValuesInVector = newRelevantLength;

 }
 
 } // namespace JSC
 }
 
 } // namespace JSC