JavaScriptCore-7600.1.4.16.1.tar.gz

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

diff --git a/runtime/JSArray.cpp b/runtime/JSArray.cpp
index 473ba1d3eec4973a48a2131dc1c36faf284fe74f..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, 2009 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,860 +24,995 @@
 #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 "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>

 
 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
-
-// The value BASE_VECTOR_LEN is the maximum number of vector elements we'll allocate
-// for an array that was created with a sepcified length (e.g. a = new Array(123))
-#define BASE_VECTOR_LEN 4U
-    
-// The upper bound to the size we'll grow a zero length array when the first element
-// is added.
-#define FIRST_VECTOR_GROW 4U
-
-// Our policy for when to use a vector and when to use a sparse map.
-// For all array indices under MIN_SPARSE_ARRAY_INDEX, we always use a vector.
-// When indices greater than MIN_SPARSE_ARRAY_INDEX are involved, we use a vector
-// as long as it is 1/8 full. If more sparse than that, we use a map.
-static const unsigned minDensityMultiplier = 8;
-
-const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0};
-
-// We keep track of the size of the last array after it was grown.  We use this
-// as a simple heuristic for as the value to grow the next array from size 0.
-// This value is capped by the constant FIRST_VECTOR_GROW defined above.
-static unsigned lastArraySize = 0;
-
-static inline size_t storageSize(unsigned vectorLength)
-{
-    if (vectorLength > MAX_STORAGE_VECTOR_LENGTH)
-        CRASH();
-
-    // 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))));
+STATIC_ASSERT_IS_TRIVIALLY_DESTRUCTIBLE(JSArray);

 
 

-    return size;
-}
+const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, 0, 0, CREATE_METHOD_TABLE(JSArray)};

 
 

-static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
+Butterfly* createArrayButterflyInDictionaryIndexingMode(
+    VM& vm, JSCell* intendedOwner, unsigned initialLength)

 {
 {

-    return length / minDensityMultiplier <= numValues;
+    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;

 }
 
 }
 

-#if !CHECK_ARRAY_CONSISTENCY
-
-inline void JSArray::checkConsistency(ConsistencyCheckType)
+void JSArray::setLengthWritable(ExecState* exec, bool writable)

 {
 {

-}
-
-#endif
-
-JSArray::JSArray(VPtrStealingHackType)
-    : JSNonFinalObject(VPtrStealingHack)
-{
-}
-
-JSArray::JSArray(JSGlobalData& globalData, Structure* structure)
-    : JSNonFinalObject(globalData, structure)
-{
-    ASSERT(inherits(&s_info));
-
-    unsigned initialCapacity = 0;
-
-    m_storage = static_cast<ArrayStorage*>(fastZeroedMalloc(storageSize(initialCapacity)));
-    m_storage->m_allocBase = m_storage;
-    m_indexBias = 0;
-    m_vectorLength = initialCapacity;
-
-    checkConsistency();
-
-    Heap::heap(this)->reportExtraMemoryCost(storageSize(0));
-}
-
-JSArray::JSArray(JSGlobalData& globalData, Structure* structure, unsigned initialLength, ArrayCreationMode creationMode)
-    : JSNonFinalObject(globalData, structure)
-{
-    ASSERT(inherits(&s_info));
-
-    unsigned initialCapacity;
-    if (creationMode == CreateCompact)
-        initialCapacity = initialLength;
-    else
-        initialCapacity = min(BASE_VECTOR_LEN, MIN_SPARSE_ARRAY_INDEX);
-    
-    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialCapacity)));
-    m_storage->m_allocBase = m_storage;
-    m_storage->m_length = initialLength;
-    m_indexBias = 0;
-    m_vectorLength = initialCapacity;
-    m_storage->m_sparseValueMap = 0;
-    m_storage->subclassData = 0;
-    m_storage->reportedMapCapacity = 0;
-
-    if (creationMode == CreateCompact) {
-#if CHECK_ARRAY_CONSISTENCY
-        m_storage->m_inCompactInitialization = !!initialCapacity;
-#endif
-        m_storage->m_length = 0;
-        m_storage->m_numValuesInVector = initialCapacity;
-    } else {
-#if CHECK_ARRAY_CONSISTENCY
-        storage->m_inCompactInitialization = false;
-#endif
-        m_storage->m_length = initialLength;
-        m_storage->m_numValuesInVector = 0;
-        WriteBarrier<Unknown>* vector = m_storage->m_vector;
-        for (size_t i = 0; i < initialCapacity; ++i)
-            vector[i].clear();
-    }
-
-    checkConsistency();
-    
-    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialCapacity));
-}
-
-JSArray::JSArray(JSGlobalData& globalData, Structure* structure, const ArgList& list)
-    : JSNonFinalObject(globalData, structure)
-{
-    ASSERT(inherits(&s_info));
-
-    unsigned initialCapacity = list.size();
-    unsigned initialStorage;
-    
-    // If the ArgList is empty, allocate space for 3 entries.  This value empirically
-    // works well for benchmarks.
-    if (!initialCapacity)
-        initialStorage = 3;
-    else
-        initialStorage = initialCapacity;
-    
-    m_storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(initialStorage)));
-    m_storage->m_allocBase = m_storage;
-    m_indexBias = 0;
-    m_storage->m_length = initialCapacity;
-    m_vectorLength = initialStorage;
-    m_storage->m_numValuesInVector = initialCapacity;
-    m_storage->m_sparseValueMap = 0;
-    m_storage->subclassData = 0;
-    m_storage->reportedMapCapacity = 0;
-#if CHECK_ARRAY_CONSISTENCY
-    m_storage->m_inCompactInitialization = false;
-#endif
-
-    size_t i = 0;
-    WriteBarrier<Unknown>* vector = m_storage->m_vector;
-    ArgList::const_iterator end = list.end();
-    for (ArgList::const_iterator it = list.begin(); it != end; ++it, ++i)
-        vector[i].set(globalData, this, *it);
-    for (; i < initialStorage; i++)
-        vector[i].clear();
-
-    checkConsistency();
-
-    Heap::heap(this)->reportExtraMemoryCost(storageSize(initialStorage));
-}
+    ASSERT(isLengthWritable() || !writable);
+    if (!isLengthWritable() || writable)
+        return;

 
 

-JSArray::~JSArray()
-{
-    ASSERT(vptr() == JSGlobalData::jsArrayVPtr);
-    checkConsistency(DestructorConsistencyCheck);
+    enterDictionaryIndexingMode(exec->vm());

 
 

-    delete m_storage->m_sparseValueMap;
-    fastFree(m_storage->m_allocBase);
+    SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get();
+    ASSERT(map);
+    map->setLengthIsReadOnly();

 }
 
 }
 

-bool JSArray::getOwnPropertySlot(ExecState* exec, unsigned i, PropertySlot& slot)
+// Defined in ES5.1 15.4.5.1
+bool JSArray::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, const PropertyDescriptor& descriptor, bool throwException)

 {
 {

-    ArrayStorage* storage = m_storage;
-    
-    if (i >= storage->m_length) {
-        if (i > MAX_ARRAY_INDEX)
-            return getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
-        return false;
-    }
+    JSArray* array = jsCast<JSArray*>(object);

 
 

-    if (i < m_vectorLength) {
-        JSValue value = storage->m_vector[i].get();
-        if (value) {
-            slot.setValue(value);
+    // 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;
         }
             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.setValue(it->second.get());
-                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;

         }
         }

-    }

 
 

-    return JSObject::getOwnPropertySlot(exec, Identifier::from(exec, i), slot);
-}
+        // 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;
+        }

 
 

-bool JSArray::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
-{
-    if (propertyName == exec->propertyNames().length) {
-        slot.setValue(jsNumber(length()));
+        // 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. 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;
     }
 
         return true;
     }
 

-    bool isArrayIndex;
-    unsigned i = propertyName.toArrayIndex(isArrayIndex);
-    if (isArrayIndex)
-        return JSArray::getOwnPropertySlot(exec, i, slot);
+    // 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);
+    }

 
 

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

 }
 
 }
 

-bool JSArray::getOwnPropertyDescriptor(ExecState* exec, const Identifier& propertyName, PropertyDescriptor& descriptor)
+bool JSArray::getOwnPropertySlot(JSObject* object, ExecState* exec, PropertyName propertyName, PropertySlot& slot)

 {
 {

+    JSArray* thisObject = jsCast<JSArray*>(object);

     if (propertyName == exec->propertyNames().length) {
     if (propertyName == exec->propertyNames().length) {

-        descriptor.setDescriptor(jsNumber(length()), DontDelete | DontEnum);
+        unsigned attributes = thisObject->isLengthWritable() ? DontDelete | DontEnum : DontDelete | DontEnum | ReadOnly;
+        slot.setValue(thisObject, attributes, jsNumber(thisObject->length()));

         return true;
     }
 
         return true;
     }
 

-    ArrayStorage* storage = m_storage;
-    
-    bool isArrayIndex;
-    unsigned i = propertyName.toArrayIndex(isArrayIndex);
-    if (isArrayIndex) {
-        if (i >= storage->m_length)
-            return false;
-        if (i < m_vectorLength) {
-            WriteBarrier<Unknown>& value = storage->m_vector[i];
-            if (value) {
-                descriptor.setDescriptor(value.get(), 0);
-                return true;
-            }
-        } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
-            if (i >= MIN_SPARSE_ARRAY_INDEX) {
-                SparseArrayValueMap::iterator it = map->find(i);
-                if (it != map->end()) {
-                    descriptor.setDescriptor(it->second.get(), 0);
-                    return true;
-                }
-            }
-        }
-    }
-    return JSObject::getOwnPropertyDescriptor(exec, propertyName, descriptor);
+    return JSObject::getOwnPropertySlot(thisObject, exec, propertyName, slot);

 }
 
 // ECMA 15.4.5.1
 }
 
 // ECMA 15.4.5.1

-void JSArray::put(ExecState* exec, const Identifier& propertyName, JSValue value, PutPropertySlot& slot)
+void JSArray::put(JSCell* cell, ExecState* exec, PropertyName propertyName, JSValue value, PutPropertySlot& slot)

 {
 {

-    bool isArrayIndex;
-    unsigned i = propertyName.toArrayIndex(isArrayIndex);
-    if (isArrayIndex) {
-        put(exec, i, value);
-        return;
-    }
+    JSArray* thisObject = jsCast<JSArray*>(cell);

 
     if (propertyName == exec->propertyNames().length) {
         unsigned newLength = value.toUInt32(exec);
         if (value.toNumber(exec) != static_cast<double>(newLength)) {
 
     if (propertyName == exec->propertyNames().length) {
         unsigned newLength = value.toUInt32(exec);
         if (value.toNumber(exec) != static_cast<double>(newLength)) {

-            throwError(exec, createRangeError(exec, "Invalid array length."));
+            exec->vm().throwException(exec, createRangeError(exec, ASCIILiteral("Invalid array length")));

             return;
         }
             return;
         }

-        setLength(newLength);
+        thisObject->setLength(exec, newLength, slot.isStrictMode());

         return;
     }
 
         return;
     }
 

-    JSObject::put(exec, propertyName, value, slot);
+    JSObject::put(thisObject, exec, propertyName, value, slot);

 }
 
 }
 

-void JSArray::put(ExecState* exec, unsigned i, JSValue value)
+bool JSArray::deleteProperty(JSCell* cell, ExecState* exec, PropertyName propertyName)

 {
 {

-    checkConsistency();
-
-    ArrayStorage* storage = m_storage;
-
-    unsigned length = storage->m_length;
-    if (i >= length && i <= MAX_ARRAY_INDEX) {
-        length = i + 1;
-        storage->m_length = length;
-    }
+    JSArray* thisObject = jsCast<JSArray*>(cell);

 
 

-    if (i < m_vectorLength) {
-        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
-        if (valueSlot) {
-            valueSlot.set(exec->globalData(), this, value);
-            checkConsistency();
-            return;
-        }
-        valueSlot.set(exec->globalData(), this, value);
-        ++storage->m_numValuesInVector;
-        checkConsistency();
-        return;
-    }
+    if (propertyName == exec->propertyNames().length)
+        return false;

 
 

-    putSlowCase(exec, i, value);
+    return JSObject::deleteProperty(thisObject, exec, propertyName);

 }
 
 }
 

-NEVER_INLINE void JSArray::putSlowCase(ExecState* exec, unsigned i, JSValue value)
+static int compareKeysForQSort(const void* a, const void* b)

 {
 {

-    ArrayStorage* storage = m_storage;
-    
-    SparseArrayValueMap* map = storage->m_sparseValueMap;
+    unsigned da = *static_cast<const unsigned*>(a);
+    unsigned db = *static_cast<const unsigned*>(b);
+    return (da > db) - (da < db);
+}

 
 

-    if (i >= MIN_SPARSE_ARRAY_INDEX) {
-        if (i > MAX_ARRAY_INDEX) {
-            PutPropertySlot slot;
-            put(exec, Identifier::from(exec, i), value, slot);
-            return;
-        }
+void JSArray::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
+{
+    JSArray* thisObject = jsCast<JSArray*>(object);

 
 

-        // 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 MIN_SPARSE_ARRAY_INDEX) - but this makes the check much faster.
-        if ((i > MAX_STORAGE_VECTOR_INDEX) || !isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
-            if (!map) {
-                map = new SparseArrayValueMap;
-                storage->m_sparseValueMap = map;
-            }
+    if (mode == IncludeDontEnumProperties)
+        propertyNames.add(exec->propertyNames().length);

 
 

-            WriteBarrier<Unknown> temp;
-            pair<SparseArrayValueMap::iterator, bool> result = map->add(i, temp);
-            result.first->second.set(exec->globalData(), this, value);
-            if (!result.second) // pre-existing entry
-                return;
+    JSObject::getOwnNonIndexPropertyNames(thisObject, exec, propertyNames, mode);
+}

 
 

-            size_t capacity = map->capacity();
-            if (capacity != storage->reportedMapCapacity) {
-                Heap::heap(this)->reportExtraMemoryCost((capacity - storage->reportedMapCapacity) * (sizeof(unsigned) + sizeof(JSValue)));
-                storage->reportedMapCapacity = capacity;
-            }
-            return;
-        }
+// 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 = 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;
+    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;

     }
 
     }
 

-    // 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].set(exec->globalData(), this, value);
-            ++storage->m_numValuesInVector;
-            checkConsistency();
-        } else
-            throwOutOfMemoryError(exec);
-        return;
+    // 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);

     }
 
     }
 

-    // Decide how many values it would be best to move from the map.
-    unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
-    unsigned newVectorLength = getNewVectorLength(i + 1);
-    for (unsigned j = max(m_vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
-        newNumValuesInVector += map->contains(j);
-    if (i >= MIN_SPARSE_ARRAY_INDEX)
-        newNumValuesInVector -= map->contains(i);
-    if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
-        unsigned needLength = max(i + 1, storage->m_length);
-        unsigned proposedNewNumValuesInVector = newNumValuesInVector;
-        // If newVectorLength is already the maximum - MAX_STORAGE_VECTOR_LENGTH - then do not attempt to grow any further.
-        while ((newVectorLength < needLength) && (newVectorLength < MAX_STORAGE_VECTOR_LENGTH)) {
-            unsigned proposedNewVectorLength = getNewVectorLength(newVectorLength + 1);
-            for (unsigned j = max(newVectorLength, MIN_SPARSE_ARRAY_INDEX); j < proposedNewVectorLength; ++j)
-                proposedNewNumValuesInVector += map->contains(j);
-            if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector))
-                break;
-            newVectorLength = proposedNewVectorLength;
-            newNumValuesInVector = proposedNewNumValuesInVector;
-        }
-    }
+    unsigned newVectorLength = requiredVectorLength + postCapacity;
+    unsigned newIndexBias = newStorageCapacity - newVectorLength;

 
 

-    void* baseStorage = storage->m_allocBase;
+    Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, newIndexBias, propertyCapacity);

 
 

-    if ((unsigned)m_indexBias > (MAX_STORAGE_VECTOR_LENGTH - newVectorLength)
-        || !tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage)) {
-        throwOutOfMemoryError(exec);
-        return;
+    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();

     }
 
     }
 

-    m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
-    m_storage->m_allocBase = baseStorage;
-    storage = m_storage;
-    
-    unsigned vectorLength = m_vectorLength;
-    WriteBarrier<Unknown>* vector = storage->m_vector;
+    newButterfly->arrayStorage()->setVectorLength(newVectorLength);
+    newButterfly->arrayStorage()->m_indexBias = newIndexBias;
+    setButterflyWithoutChangingStructure(vm, newButterfly);

 
 

-    if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
-        for (unsigned j = vectorLength; j < newVectorLength; ++j)
-            vector[j].clear();
-        if (i > MIN_SPARSE_ARRAY_INDEX)
-            map->remove(i);
-    } else {
-        for (unsigned j = vectorLength; j < max(vectorLength, MIN_SPARSE_ARRAY_INDEX); ++j)
-            vector[j].clear();
-        JSGlobalData& globalData = exec->globalData();
-        for (unsigned j = max(vectorLength, MIN_SPARSE_ARRAY_INDEX); j < newVectorLength; ++j)
-            vector[j].set(globalData, this, map->take(j).get());
-    }
+    return true;
+}

 
 

-    ASSERT(i < newVectorLength);
+bool JSArray::setLengthWithArrayStorage(ExecState* exec, unsigned newLength, bool throwException, ArrayStorage* storage)
+{
+    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);
+            }

 
 

-    m_vectorLength = newVectorLength;
-    storage->m_numValuesInVector = newNumValuesInVector;
+            // 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();
+            }
+        }
+    }

 
 

-    storage->m_vector[i].set(exec->globalData(), this, value);
+    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;
+        }
+    }

 
 

-    checkConsistency();
+    storage->setLength(newLength);

 
 

-    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
+    return true;

 }
 
 }
 

-bool JSArray::deleteProperty(ExecState* exec, const Identifier& propertyName)
+bool JSArray::setLength(ExecState* exec, unsigned newLength, bool throwException)

 {
 {

-    bool isArrayIndex;
-    unsigned i = propertyName.toArrayIndex(isArrayIndex);
-    if (isArrayIndex)
-        return deleteProperty(exec, i);
-
-    if (propertyName == exec->propertyNames().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;
         return false;

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

 }
 
 }
 

-bool JSArray::deleteProperty(ExecState* exec, unsigned i)
+JSValue JSArray::pop(ExecState* exec)

 {
 {

-    checkConsistency();
-
-    ArrayStorage* storage = m_storage;
-    
-    if (i < m_vectorLength) {
-        WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
-        if (!valueSlot) {
-            checkConsistency();
-            return false;
+    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.clear();
-        --storage->m_numValuesInVector;
-        checkConsistency();
-        return true;
+        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();
+        }

 
 

-    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;
+        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;

     }
     }

-
-    checkConsistency();
-
-    if (i > MAX_ARRAY_INDEX)
-        return deleteProperty(exec, Identifier::from(exec, i));
-
-    return false;
-}
-
-void JSArray::getOwnPropertyNames(ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
-{
-    // FIXME: Filling PropertyNameArray with an identifier for every integer
-    // is incredibly inefficient for large arrays. We need a different approach,
-    // which almost certainly means a different structure for PropertyNameArray.
-
-    ArrayStorage* storage = m_storage;
-    
-    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
-    for (unsigned i = 0; i < usedVectorLength; ++i) {
-        if (storage->m_vector[i])
-            propertyNames.add(Identifier::from(exec, i));
+        
+    default:
+        CRASH();
+        return JSValue();

     }
     }

-
-    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));
+    
+    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();

     }
     }

-
-    if (mode == IncludeDontEnumProperties)
-        propertyNames.add(exec->propertyNames().length);
-
-    JSObject::getOwnPropertyNames(exec, propertyNames, mode);
+    // Call the [[Put]] internal method of O with arguments "length", indx, and true.
+    setLength(exec, index, true);
+    // Return element.
+    return element;

 }
 
 }
 

-ALWAYS_INLINE unsigned JSArray::getNewVectorLength(unsigned desiredLength)
+// 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)

 {
 {

-    ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);
+    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;
+        }

 
 

-    unsigned increasedLength;
-    unsigned maxInitLength = min(m_storage->m_length, 100000U);
+        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;
+        }
+        
+        putByIndexBeyondVectorLengthWithoutAttributes<Int32Shape>(exec, length, value);
+        return;
+    }

 
 

-    if (desiredLength < maxInitLength)
-        increasedLength = maxInitLength;
-    else if (!m_vectorLength)
-        increasedLength = max(desiredLength, lastArraySize);
-    else {
-        // Mathematically equivalent to:
-        //   increasedLength = (newLength * 3 + 1) / 2;
-        // or:
-        //   increasedLength = (unsigned)ceil(newLength * 1.5));
-        // This form is not prone to internal overflow.
-        increasedLength = desiredLength + (desiredLength >> 1) + (desiredLength & 1);
+    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;

     }
     }

+        
+    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;
+        }

 
 

-    ASSERT(increasedLength >= desiredLength);
+        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;
+    }
+        
+    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;
+        }

 
 

-    lastArraySize = min(increasedLength, FIRST_VECTOR_GROW);
+        // 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;
+        }

 
 

-    return min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
+        // Handled the same as putIndex.
+        putByIndexBeyondVectorLengthWithArrayStorage(exec, storage->length(), value, true, storage);
+        break;
+    }
+        
+    default:
+        RELEASE_ASSERT_NOT_REACHED();
+    }

 }
 
 }
 

-bool JSArray::increaseVectorLength(unsigned newLength)
+bool JSArray::shiftCountWithArrayStorage(VM& vm, 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 vectorLength = m_vectorLength;
-    ASSERT(newLength > vectorLength);
-    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
-    unsigned newVectorLength = getNewVectorLength(newLength);
-    void* baseStorage = storage->m_allocBase;
-
-    if ((unsigned)m_indexBias > (MAX_STORAGE_VECTOR_LENGTH - newVectorLength)
-        || !tryFastRealloc(baseStorage, storageSize(newVectorLength + m_indexBias)).getValue(baseStorage))
+    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;

+    }

 
 

-    storage = m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(baseStorage) + m_indexBias * sizeof(JSValue));
-    m_storage->m_allocBase = baseStorage;
-
-    WriteBarrier<Unknown>* vector = storage->m_vector;
-    for (unsigned i = vectorLength; i < newVectorLength; ++i)
-        vector[i].clear();
-
-    m_vectorLength = newVectorLength;
+    if (!oldLength)
+        return true;

     
     

-    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
-
-    return true;
-}
-
-bool JSArray::increaseVectorPrefixLength(unsigned newLength)
-{
-    // 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.
+    unsigned length = oldLength - count;

     
     

-    ArrayStorage* storage = m_storage;
+    storage->m_numValuesInVector -= count;
+    storage->setLength(length);

     
     

-    unsigned vectorLength = m_vectorLength;
-    ASSERT(newLength > vectorLength);
-    ASSERT(newLength <= MAX_STORAGE_VECTOR_INDEX);
-    unsigned newVectorLength = getNewVectorLength(newLength);
-
-    if ((unsigned)m_indexBias > (MAX_STORAGE_VECTOR_LENGTH - newVectorLength))
-        return false;
-    void* newBaseStorage = fastMalloc(storageSize(newVectorLength + m_indexBias));
-    if (!newBaseStorage)
-        return false;
+    unsigned vectorLength = storage->vectorLength();
+    if (!vectorLength)
+        return true;

     
     

-    m_indexBias += newVectorLength - newLength;
+    if (startIndex >= vectorLength)
+        return true;

     
     

-    m_storage = reinterpret_cast_ptr<ArrayStorage*>(static_cast<char*>(newBaseStorage) + m_indexBias * sizeof(JSValue));
-
-    memcpy(m_storage, storage, storageSize(0));
-    memcpy(&m_storage->m_vector[newLength - m_vectorLength], &storage->m_vector[0], vectorLength * sizeof(JSValue));
+    if (startIndex + count > vectorLength)
+        count = vectorLength - startIndex;

     
     

-    m_storage->m_allocBase = newBaseStorage;
-    m_vectorLength = newLength;
+    unsigned usedVectorLength = min(vectorLength, oldLength);

     
     

-    fastFree(storage->m_allocBase);
-    ASSERT(newLength > vectorLength);
-    unsigned delta = newLength - vectorLength;
-    for (unsigned i = 0; i < delta; i++)
-        m_storage->m_vector[i].clear();
-    Heap::heap(this)->reportExtraMemoryCost(storageSize(newVectorLength) - storageSize(vectorLength));
+    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.
+    }

     
     return true;
 }
     
     return true;
 }

-    

 
 

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

 {
 {

-    ArrayStorage* storage = m_storage;
+    VM& vm = exec->vm();
+    RELEASE_ASSERT(count > 0);

     
     

-#if CHECK_ARRAY_CONSISTENCY
-    if (!storage->m_inCompactInitialization)
-        checkConsistency();
-    else
-        storage->m_inCompactInitialization = false;
-#endif
-
-    unsigned length = storage->m_length;
-
-    if (newLength < length) {
-        unsigned usedVectorLength = min(length, m_vectorLength);
-        for (unsigned i = newLength; i < usedVectorLength; ++i) {
-            WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
-            bool hadValue = valueSlot;
-            valueSlot.clear();
-            storage->m_numValuesInVector -= hadValue;
+    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));

         }
 
         }
 

-        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 = end; i < oldLength; ++i)
+            m_butterfly->contiguous()[i].clear();
+        
+        m_butterfly->setPublicLength(oldLength - count);
+        return true;
+    }
+        
+    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;

     }
     }

-
-    storage->m_length = newLength;
-
-    checkConsistency();

 }
 
 }
 

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

 {
 {

-    checkConsistency();
-
-    ArrayStorage* storage = m_storage;
-    
-    unsigned length = storage->m_length;
-    if (!length)
-        return jsUndefined();
+    unsigned length = storage->length();

 
 

-    --length;
+    RELEASE_ASSERT(startIndex <= length);

 
 

-    JSValue result;
-
-    if (length < m_vectorLength) {
-        WriteBarrier<Unknown>& valueSlot = storage->m_vector[length];
-        if (valueSlot) {
-            --storage->m_numValuesInVector;
-            result = valueSlot.get();
-            valueSlot.clear();
-        } else
-            result = jsUndefined();
-    } else {
-        result = jsUndefined();
-        if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
-            SparseArrayValueMap::iterator it = map->find(length);
-            if (it != map->end()) {
-                result = it->second.get();
-                map->remove(it);
-                if (map->isEmpty()) {
-                    delete map;
-                    storage->m_sparseValueMap = 0;
-                }
-            }
-        }
-    }
+    // 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;

 
 

-    storage->m_length = length;
+    bool moveFront = !startIndex || startIndex < length / 2;

 
 

-    checkConsistency();
+    unsigned vectorLength = storage->vectorLength();

 
 

-    return result;
-}
-
-void JSArray::push(ExecState* exec, JSValue value)
-{
-    checkConsistency();
-    
-    ArrayStorage* storage = m_storage;
-
-    if (storage->m_length < m_vectorLength) {
-        storage->m_vector[storage->m_length].set(exec->globalData(), this, value);
-        ++storage->m_numValuesInVector;
-        ++storage->m_length;
-        checkConsistency();
-        return;
+    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;

     }
 
     }
 

-    if (storage->m_length < MIN_SPARSE_ARRAY_INDEX) {
-        SparseArrayValueMap* map = storage->m_sparseValueMap;
-        if (!map || map->isEmpty()) {
-            if (increaseVectorLength(storage->m_length + 1)) {
-                storage = m_storage;
-                storage->m_vector[storage->m_length].set(exec->globalData(), this, value);
-                ++storage->m_numValuesInVector;
-                ++storage->m_length;
-                checkConsistency();
-                return;
-            }
-            checkConsistency();
-            throwOutOfMemoryError(exec);
-            return;
-        }
+    WriteBarrier<Unknown>* vector = storage->m_vector;
+
+    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));

     }
 
     }
 

-    putSlowCase(exec, storage->m_length++, value);
+    for (unsigned i = 0; i < count; i++)
+        vector[i + startIndex].clear();
+    return true;

 }
 
 }
 

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

 {
 {

-    ASSERT(count > 0);
-    
-    ArrayStorage* storage = m_storage;
-    
-    unsigned oldLength = storage->m_length;
-    
-    if (!oldLength)
-        return;
-    
-    if (oldLength != storage->m_numValuesInVector) {
-        // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
-        // which means we need to go through each entry looking for the the "empty"
-        // slots and then fill them with possible properties.  See ECMA spec.
-        // 15.4.4.9 steps 11 through 13.
-        for (unsigned i = count; i < oldLength; ++i) {
-            if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
-                PropertySlot slot(this);
-                JSValue p = prototype();
-                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
-                    put(exec, i, slot.getValue(exec, i));
-            }
-        }
-
-        storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
+    switch (indexingType()) {
+    case ArrayClass:
+    case ArrayWithUndecided:
+        // We could handle this. But it shouldn't ever come up, so we won't.
+        return false;

 
 

-        // Need to decrement numValuesInvector based on number of real entries
-        for (unsigned i = 0; i < (unsigned)count; ++i)
-            if ((i < m_vectorLength) && (storage->m_vector[i]))
-                --storage->m_numValuesInVector;
-    } else
-        storage->m_numValuesInVector -= count;
-    
-    storage->m_length -= count;
-    
-    if (m_vectorLength) {
-        count = min(m_vectorLength, (unsigned)count);
+    case ArrayWithInt32:
+    case ArrayWithContiguous: {
+        unsigned oldLength = m_butterfly->publicLength();

         
         

-        m_vectorLength -= count;
+        // 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()));

         
         

-        if (m_vectorLength) {
-            char* newBaseStorage = reinterpret_cast<char*>(storage) + count * sizeof(JSValue);
-            memmove(newBaseStorage, storage, storageSize(0));
-            m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
+        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()));
+        }

 
 

-            m_indexBias += count;
+        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;

     }
     }

-}
-    
-void JSArray::unshiftCount(ExecState* exec, int count)
-{
-    ArrayStorage* storage = m_storage;
+        
+    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()));
+        }

 
 

-    ASSERT(m_indexBias >= 0);
-    ASSERT(count >= 0);
-    
-    unsigned length = storage->m_length;
-    
-    if (length != storage->m_numValuesInVector) {
-        // If m_length and m_numValuesInVector aren't the same, we have a sparse vector
-        // which means we need to go through each entry looking for the the "empty"
-        // slots and then fill them with possible properties.  See ECMA spec.
-        // 15.4.4.13 steps 8 through 10.
-        for (unsigned i = 0; i < length; ++i) {
-            if ((i >= m_vectorLength) || (!m_storage->m_vector[i])) {
-                PropertySlot slot(this);
-                JSValue p = prototype();
-                if ((!p.isNull()) && (asObject(p)->getPropertySlot(exec, i, slot)))
-                    put(exec, i, slot.getValue(exec, i));
-            }
+        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;

     }
     }

-    
-    storage = m_storage; // The put() above could have grown the vector and realloc'ed storage.
-    
-    if (m_indexBias >= count) {
-        m_indexBias -= count;
-        char* newBaseStorage = reinterpret_cast<char*>(storage) - count * sizeof(JSValue);
-        memmove(newBaseStorage, storage, storageSize(0));
-        m_storage = reinterpret_cast_ptr<ArrayStorage*>(newBaseStorage);
-        m_vectorLength += count;
-    } else if ((unsigned)count > (MAX_STORAGE_VECTOR_LENGTH - m_vectorLength)
-        || !increaseVectorPrefixLength(m_vectorLength + count)) {
-        throwOutOfMemoryError(exec);
-        return;
+        
+    case ArrayWithArrayStorage:
+    case ArrayWithSlowPutArrayStorage:
+        return unshiftCountWithArrayStorage(exec, startIndex, count, arrayStorage());
+        
+    default:
+        CRASH();
+        return false;

     }
     }

+}

 
 

-    WriteBarrier<Unknown>* vector = m_storage->m_vector;
-    for (int i = 0; i < count; i++)
-        vector[i].clear();
+static int compareNumbersForQSortWithInt32(const void* a, const void* b)
+{
+    int32_t ia = static_cast<const JSValue*>(a)->asInt32();
+    int32_t ib = static_cast<const JSValue*>(b)->asInt32();
+    return ia - ib;

 }
 
 }
 

-void JSArray::visitChildren(SlotVisitor& visitor)
+static int compareNumbersForQSortWithDouble(const void* a, const void* b)

 {
 {

-    ASSERT_GC_OBJECT_INHERITS(this, &s_info);
-    COMPILE_ASSERT(StructureFlags & OverridesVisitChildren, OverridesVisitChildrenWithoutSettingFlag);
-    ASSERT(structure()->typeInfo().overridesVisitChildren());
-    visitChildrenDirect(visitor);
+    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);
 }
 


@@ -888,107 +1023,268 @@ static int compareByStringPairForQSort(const void* a, const void* b)
     return codePointCompare(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)

 {
 {

-    ArrayStorage* storage = m_storage;
-
-    unsigned lengthNotIncludingUndefined = compactForSorting();
-    if (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 = storage->m_numValuesInVector;
-    for (size_t i = 0; i < size; ++i) {
-        if (!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(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)

 {
 {

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

 
 

-    unsigned lengthNotIncludingUndefined = compactForSorting();
-    if (storage->m_sparseValueMap) {
-        throwOutOfMemoryError(exec);
+    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);
     Heap::heap(this)->pushTempSortVector(&values);

+        
+    bool isSortingPrimitiveValues = true;

 
 

-    for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
-        JSValue value = storage->m_vector[i].get();
+    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: 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);
-
+        
+    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;
     }
     if (exec->hadException()) {
         Heap::heap(this)->popTempSortVector(&values);
         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.
     // If the toString function changed the length of the array or vector storage,
     // increase the length to handle the orignal number of actual values.

-    if (m_vectorLength < lengthNotIncludingUndefined)
-        increaseVectorLength(lengthNotIncludingUndefined);
-    if (storage->m_length < lengthNotIncludingUndefined)
-        storage->m_length = lengthNotIncludingUndefined;
-
-    JSGlobalData& globalData = exec->globalData();
-    for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
-        storage->m_vector[i].set(globalData, this, values[i].first);
+    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();
+    }

 
 

+    for (size_t i = 0; i < relevantLength; i++)
+        ContiguousTypeAccessor<arrayIndexingType>::setWithValue(vm, this, data, i, values[i].first);
+    

     Heap::heap(this)->popTempSortVector(&values);
     Heap::heap(this)->popTempSortVector(&values);

+}
+
+void JSArray::sort(ExecState* exec)
+{
+    ASSERT(!inSparseIndexingMode());

     
     

-    checkConsistency(SortConsistencyCheck);
+    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 {


@@ -1006,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; }


@@ -1050,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(m_exec));
+            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.
     }


@@ -1069,58 +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();
-
-    ArrayStorage* storage = m_storage;
-
+    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(storage->m_length <= static_cast<unsigned>(std::numeric_limits<int>::max()));
-    if (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;

-
-    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
-    unsigned nodeCount = usedVectorLength + (storage->m_sparseValueMap ? storage->m_sparseValueMap->size() : 0);
-
+        
+    unsigned usedVectorLength = relevantLength<arrayIndexingType>();
+    unsigned nodeCount = usedVectorLength;
+        

     if (!nodeCount)
         return;
     if (!nodeCount)
         return;

-
+        

     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.grow(nodeCount);
     tree.abstractor().m_nodes.grow(nodeCount);

-
+        

     if (callType == CallTypeJS)
     if (callType == CallTypeJS)

-        tree.abstractor().m_cachedCall = adoptPtr(new CachedCall(exec, asFunction(compareFunction), 2));
-
+        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 = storage->m_vector[numDefined].get();
+        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 = storage->m_vector[i].get();
+        if (i >= m_butterfly->vectorLength())
+            break;
+        JSValue v = getHolyIndexQuickly(i);

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


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

-
+    

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

-
-    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
-        newUsedVectorLength += map->size();
-        if (newUsedVectorLength > m_vectorLength) {
-            // Check that it is possible to allocate an array large enough to hold all the entries.
-            if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength)) {
-                throwOutOfMemoryError(exec);
-                return;
-            }
-        }

         
         

-        storage = m_storage;
-
-        SparseArrayValueMap::iterator end = map->end();
-        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
-            tree.abstractor().m_nodes[numDefined].value = it->second.get();
-            tree.insert(numDefined);
-            ++numDefined;
-        }
-
-        delete map;
-        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);

-    JSGlobalData& globalData = exec->globalData();
-    for (unsigned i = 0; i < numDefined; ++i) {
-        storage->m_vector[i].set(globalData, this, 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)
-        storage->m_vector[i].setUndefined();
+    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)
-        storage->m_vector[i].clear();
+    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;
+}
+
+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;
+
+    case ArrayWithDouble:
+        sortVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
+        return;

 
 

-    storage->m_numValuesInVector = newUsedVectorLength;
+    case ArrayWithContiguous:
+        sortVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
+        return;

 
 

-    checkConsistency(SortConsistencyCheck);
+    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)
 {

-    ArrayStorage* storage = m_storage;
-
-    WriteBarrier<Unknown>* vector = storage->m_vector;
-    unsigned vectorEnd = min(storage->m_length, m_vectorLength);

     unsigned i = 0;
     unsigned i = 0;

+    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 < vectorEnd; ++i) {
         WriteBarrier<Unknown>& v = vector[i];
         if (!v)
             break;
         args.append(v.get());
     }

-
-    for (; i < storage->m_length; ++i)
+    
+    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);
-    WriteBarrier<Unknown>* vector = m_storage->m_vector;
-    unsigned vectorEnd = min(maxSize, m_vectorLength);
-    unsigned i = 0;
+    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;
     for (; i < vectorEnd; ++i) {
         WriteBarrier<Unknown>& v = vector[i];
         if (!v)
             break;

-        buffer[i] = v.get();
+        callFrame->setArgument(i - firstVarArgOffset, v.get());

     }
     }

-
-    for (; i < maxSize; ++i)
-        buffer[i] = get(exec, i);
+    
+    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;
-
-    unsigned usedVectorLength = min(storage->m_length, m_vectorLength);
+    ASSERT(!inSparseIndexingMode());
+    ASSERT(arrayIndexingType == indexingType());

 
 

-    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].get();
+        
+    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].get();
+        
+    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++].setWithoutWriteBarrier(v);
-        }
-    }
-
-    unsigned newUsedVectorLength = numDefined + numUndefined;
-
-    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
-        newUsedVectorLength += map->size();
-        if (newUsedVectorLength > m_vectorLength) {
-            // Check that it is possible to allocate an array large enough to hold all the entries - if not,
-            // exception is thrown by caller.
-            if ((newUsedVectorLength > MAX_STORAGE_VECTOR_LENGTH) || !increaseVectorLength(newUsedVectorLength))
-                return 0;
-
-            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++].setWithoutWriteBarrier(it->second.get());
-
-        delete map;
-        storage->m_sparseValueMap = 0;

     }
     }

-
-    for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
-        storage->m_vector[i].setUndefined();
-    for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
-        storage->m_vector[i].clear();
-
-    storage->m_numValuesInVector = newUsedVectorLength;
-
-    checkConsistency(SortConsistencyCheck);
-
-    return numDefined;
-}
-
-void* JSArray::subclassData() const
-{
-    return m_storage->subclassData;
-}
-
-void JSArray::setSubclassData(void* d)
-{
-    m_storage->subclassData = d;
-}
-
-#if CHECK_ARRAY_CONSISTENCY
-
-void JSArray::checkConsistency(ConsistencyCheckType type)
-{
-    ArrayStorage* storage = m_storage;
-
-    ASSERT(storage);
-    if (type == SortConsistencyCheck)
-        ASSERT(!storage->m_sparseValueMap);
-
-    unsigned numValuesInVector = 0;
-    for (unsigned i = 0; i < m_vectorLength; ++i) {
-        if (JSValue value = storage->m_vector[i]) {
-            ASSERT(i < storage->m_length);
-            if (type != DestructorConsistencyCheck)
-                value.isUndefined(); // Likely to crash if the object was deallocated.
-            ++numValuesInVector;
-        } else {
-            if (type == SortConsistencyCheck)
-                ASSERT(i >= 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 == storage->m_numValuesInVector);
-    ASSERT(numValuesInVector <= storage->m_length);
-
-    if (storage->m_sparseValueMap) {
-        SparseArrayValueMap::iterator end = storage->m_sparseValueMap->end();
-        for (SparseArrayValueMap::iterator it = storage->m_sparseValueMap->begin(); it != end; ++it) {
-            unsigned index = it->first;
-            ASSERT(index < storage->m_length);
-            ASSERT(index >= storage->m_vectorLength);
-            ASSERT(index <= MAX_ARRAY_INDEX);
-            ASSERT(it->second);
-            if (type != DestructorConsistencyCheck)
-                it->second.isUndefined(); // 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
+    if (hasAnyArrayStorage(arrayIndexingType))
+        arrayStorage()->m_numValuesInVector = newRelevantLength;
+}

 
 } // namespace JSC
 
 } // namespace JSC