File indexing completed on 2024-05-12 15:43:14

 /*
  *  This file is part of the KDE libraries
  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
  *  Copyright (C) 2003, 2007, 2008 Apple Inc. All rights reserved.
  *  Copyright (C) 2003 Peter Kelly (pmk@post.com)
  *  Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
  *
  *  This library is free software; you can redistribute it and/or
  *  modify it under the terms of the GNU Lesser General Public
  *  License as published by the Free Software Foundation; either
  *  version 2 of the License, or (at your option) any later version.
  *
  *  This library is distributed in the hope that it will be useful,
  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  *  Lesser General Public License for more details.
  *
  *  You should have received a copy of the GNU Lesser General Public
  *  License along with this library; if not, write to the Free Software
  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  *
  */
 
 #include "array_instance.h"
 
 #include "PropertyNameArray.h"
 #include "JSVariableObject.h"
 #include <wtf/Assertions.h>
 #include <wtf/HashMap.h>
 
 #include <algorithm>
 #include <stdio.h>
 
 using std::min;
 using std::max;
 
 namespace KJS
 {
 
 struct ArrayEntity {
     ArrayEntity()
         : value(nullptr),
           attributes(0)
     {
     }
 
     ArrayEntity(JSValue *jsVal, uint32_t attr)
         : value(jsVal),
           attributes(attr)
     {
     }
 
     JSValue *value;
     uint32_t attributes;
 };
 
 typedef HashMap<unsigned, ArrayEntity> SparseArrayValueMap;
 
 struct ArrayStorage {
     unsigned m_numValuesInVector;
     SparseArrayValueMap *m_sparseValueMap;
     ArrayEntity m_vector[1];
 };
 
 // (2^32)-1
 static const unsigned maxArrayLength = 0xFFFFFFFFU;
 // 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer
 static const unsigned maxArrayIndex = 0xFFFFFFFEU;
 
 // Our policy for when to use a vector and when to use a sparse map.
 // For all array indices under sparseArrayCutoff, we always use a vector.
 // When indices greater than sparseArrayCutoff 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 sparseArrayCutoff = 10000;
 static const unsigned minDensityMultiplier = 8;
 
 static const unsigned mergeSortCutoff = 10000;
 
 const ClassInfo ArrayInstance::info = {"Array", nullptr, nullptr, nullptr};
 
 static inline size_t storageSize(unsigned vectorLength)
 {
     return sizeof(ArrayStorage) - sizeof(ArrayEntity) + vectorLength * sizeof(ArrayEntity);
 }
 
 static inline unsigned increasedVectorLength(unsigned newLength)
 {
     return (newLength * 3 + 1) / 2;
 }
 
 static inline bool isDenseEnoughForVector(unsigned length, unsigned numValues)
 {
     return length / minDensityMultiplier <= numValues;
 }
 
 ArrayInstance::ArrayInstance(JSObject *prototype, unsigned initialLength)
     : JSObject(prototype)
 {
     unsigned initialCapacity = min(initialLength, sparseArrayCutoff);
 
     m_length = initialLength;
     m_vectorLength = initialCapacity;
     m_storage = static_cast<ArrayStorage *>(fastCalloc(storageSize(initialCapacity), 1));
     m_lengthAttributes = DontDelete | DontEnum;
 
     Collector::reportExtraMemoryCost(initialCapacity * sizeof(ArrayEntity));
 }
 
 ArrayInstance::ArrayInstance(JSObject *prototype, const List &list)
     : JSObject(prototype)
 {
     unsigned length = list.size();
 
     m_length = length;
     m_vectorLength = length;
     m_lengthAttributes = DontDelete | DontEnum;
 
     ArrayStorage *storage = static_cast<ArrayStorage *>(fastMalloc(storageSize(length)));
 
     storage->m_numValuesInVector = length;
     storage->m_sparseValueMap = nullptr;
 
     ListIterator it = list.begin();
     for (unsigned i = 0; i < length; ++i) {
         storage->m_vector[i].value = it++;
         storage->m_vector[i].attributes = 0;
     }
 
     m_storage = storage;
 
     // When the array is created non-empty, its cells are filled, so it's really no worse than
     // a property map. Therefore don't report extra memory cost.
 }
 
 ArrayInstance::~ArrayInstance()
 {
     delete m_storage->m_sparseValueMap;
     fastFree(m_storage);
 }
 
 JSValue *ArrayInstance::getItem(unsigned i) const
 {
     ASSERT(i <= maxArrayIndex);
 
     ArrayEntity *ent = getArrayEntity(i);
     if (ent) {
         return ent->value;
     }
     return jsUndefined();
 }
 
 JSValue *ArrayInstance::lengthGetter(ExecState *, JSObject *, const Identifier &, const PropertySlot &slot)
 {
     return jsNumber(static_cast<ArrayInstance *>(slot.slotBase())->m_length);
 }
 
 ALWAYS_INLINE bool ArrayInstance::inlineGetOwnPropertySlot(ExecState *exec, unsigned i, PropertySlot &slot)
 {
     if (i >= m_length) {
         if (i > maxArrayIndex) {
             return getOwnPropertySlot(exec, Identifier::from(i), slot);
         }
         return false;
     }
 
     ArrayEntity *ent = getArrayEntity(i);
     if (ent) {
         if (ent->attributes & GetterSetter) {
             GetterSetterImp *gs = static_cast<GetterSetterImp *>(ent->value);
             JSObject *getterFunc = gs->getGetter();
             if (getterFunc) {
                 slot.setGetterSlot(this, getterFunc);
             } else {
                 slot.setUndefined(this);
             }
             return true;
         }
         slot.setValueSlot(this, &ent->value);
         return true;
     }
 
     return false;
 }
 
 ArrayEntity *ArrayInstance::getArrayEntity(unsigned int i) const
 {
     if (i >= m_length) {
         return nullptr;
     }
 
     ArrayStorage *storage = m_storage;
     if (i < m_vectorLength) {
         if (storage->m_vector[i].value) {
             return &storage->m_vector[i];
         }
     }
 
     SparseArrayValueMap *map = storage->m_sparseValueMap;
     if (map && i > 0 && i <= maxArrayIndex) {
         SparseArrayValueMap::iterator it = map->find(i);
         if (it != map->end()) {
             return &it->second;
         }
     }
 
     return nullptr;
 }
 
 bool ArrayInstance::getOwnPropertySlot(ExecState *exec, const Identifier &propertyName, PropertySlot &slot)
 {
     if (propertyName == exec->propertyNames().length) {
         slot.setCustom(this, lengthGetter);
         return true;
     }
 
     bool isArrayIndex;
     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
     if (isArrayIndex) {
         return inlineGetOwnPropertySlot(exec, i, slot);
     }
 
     return JSObject::getOwnPropertySlot(exec, propertyName, slot);
 }
 
 bool ArrayInstance::getOwnPropertySlot(ExecState *exec, unsigned i, PropertySlot &slot)
 {
     return inlineGetOwnPropertySlot(exec, i, slot);
 }
 
 // ECMA 15.4.5.1
 void ArrayInstance::put(ExecState *exec, const Identifier &propertyName, JSValue *value, int attributes)
 {
     bool isArrayIndex;
     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
     if (isArrayIndex) {
         put(exec, i, value, attributes);
         return;
     }
 
     if (propertyName == exec->propertyNames().length) {
         if (m_lengthAttributes & ReadOnly) {
             return;
         }
         unsigned newLength = JSValue::toUInt32(value, exec);
         if (JSValue::toNumber(value, exec) != static_cast<double>(newLength)) {
             throwError(exec, RangeError, "Invalid array length.");
             return;
         }
         m_lengthAttributes = attributes;
         setLength(newLength);
         return;
     }
 
     JSObject::put(exec, propertyName, value, attributes);
 }
 
 void ArrayInstance::put(ExecState *exec, unsigned i, JSValue *value, int attributes)
 {
     ArrayEntity *ent = getArrayEntity(i);
     if (ent) {
         if (ent->attributes & ReadOnly) {
             return;
         }
         attributes |= ent->attributes;
 
         JSValue *gs = ent->value;
         if (gs && !JSValue::isUndefined(gs)) {
             if (ent->attributes & GetterSetter) {
                 JSObject *setterFunc = static_cast<GetterSetterImp *>(gs)->getSetter();
 
                 if (!setterFunc) {
                     if (false) { //if strict is true
                         throwError(exec, TypeError, "setting a property that has only a getter");
                     }
                     return;
                 }
 
                 List args;
                 args.append(value);
 
                 setterFunc->call(exec, this, args);
                 return;
             }
         }
     }
 
     KJS::ArrayInstance::putDirect(i, value, attributes);
 }
 
 bool ArrayInstance::deleteProperty(ExecState *exec, const Identifier &propertyName)
 {
     bool isArrayIndex;
     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
     if (isArrayIndex) {
         return deleteProperty(exec, i);
     }
 
     if (propertyName == exec->propertyNames().length) {
         return false;
     }
 
     return JSObject::deleteProperty(exec, propertyName);
 }
 
 bool ArrayInstance::deleteProperty(ExecState *exec, unsigned i)
 {
     ArrayStorage *storage = m_storage;
 
     if (i < m_vectorLength) {
         ArrayEntity *ent = &storage->m_vector[i];
         if (ent->value) {
             if (ent->attributes & DontDelete) {
                 return false;
             }
 
             JSValue *&valueSlot = ent->value;
             bool hadValue = valueSlot;
             valueSlot = nullptr;
             storage->m_numValuesInVector -= hadValue;
             ent->value = nullptr;
             return hadValue;
         }
     }
 
     if (SparseArrayValueMap *map = storage->m_sparseValueMap) {
         SparseArrayValueMap::iterator it = map->find(i);
         if (it != map->end()) {
             if ((*it).second.attributes & DontDelete) {
                 return false;
             }
             map->remove(it->first);
             return true;
         }
     }
 
     if (i > maxArrayIndex) {
         return JSObject::deleteProperty(exec, Identifier::from(i));
     }
 
     return true;
 }
 
 void ArrayInstance::getOwnPropertyNames(ExecState *exec, PropertyNameArray &propertyNames, PropertyMap::PropertyMode mode)
 {
     // FIXME: Filling PropertyNameArray with an identifier for every integer
     // is incredibly inefficient for large arrays. We need a different approach.
 
     ArrayStorage *storage = m_storage;
 
     unsigned usedVectorLength = min(m_length, m_vectorLength);
     for (unsigned i = 0; i < usedVectorLength; ++i) {
         if (storage->m_vector[i].value &&
                 (!(storage->m_vector[i].attributes & DontEnum) ||
                  mode == PropertyMap::IncludeDontEnumProperties)) {
             propertyNames.add(Identifier::from(i));
         }
     }
 
     if (SparseArrayValueMap *map = storage->m_sparseValueMap) {
         SparseArrayValueMap::iterator end = map->end();
         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
             if (!((*it).second.attributes & DontEnum) ||
                     mode == PropertyMap::IncludeDontEnumProperties) {
                 propertyNames.add(Identifier::from(it->first));
             }
     }
 
     if (mode == PropertyMap::IncludeDontEnumProperties) {
         propertyNames.add(exec->propertyNames().length);
     }
 
     JSObject::getOwnPropertyNames(exec, propertyNames, mode);
 }
 
 bool ArrayInstance::getOwnPropertyDescriptor(ExecState *exec, const Identifier &propertyName, PropertyDescriptor &descriptor)
 {
     if (propertyName == exec->propertyNames().length) {
         descriptor.setPropertyDescriptorValues(exec, jsNumber(m_length), m_lengthAttributes);
         return true;
     }
 
     bool isArrayIndex;
     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
 
     if (isArrayIndex) {
         ArrayEntity *ent = getArrayEntity(i);
         if (ent) {
             descriptor.setPropertyDescriptorValues(exec, ent->value, ent->attributes);
             return true;
         }
     }
     return JSObject::getOwnPropertyDescriptor(exec, propertyName, descriptor);
 }
 
 //ECMAScript Edition 5.1r6 - 15.4.5.1
 bool ArrayInstance::defineOwnProperty(ExecState *exec, const Identifier &propertyName, PropertyDescriptor &desc, bool shouldThrow)
 {
     PropertyDescriptor oldLenDesc;
     getOwnPropertyDescriptor(exec, exec->propertyNames().length, oldLenDesc);
     unsigned int oldLen = JSValue::toUInt32(oldLenDesc.value(), exec);
 
     //4a
     bool isArrayIndex;
     unsigned index = propertyName.toArrayIndex(&isArrayIndex);
 
     //Step 3
     if (propertyName == exec->propertyNames().length) {
         //a
         if (!desc.value()) {
             return JSObject::defineOwnProperty(exec, propertyName, desc, shouldThrow);
         }
 
         //b
         PropertyDescriptor newLenDesc(desc);
         //c
         unsigned int newLen = JSValue::toUInt32(desc.value(), exec);
         //d
         if (newLen != JSValue::toNumber(desc.value(), exec) || JSValue::toNumber(desc.value(), exec) > maxArrayLength) {
             throwError(exec, RangeError, "Index out of range");
             return false;
         }
         //e
         newLenDesc.setValue(jsNumber(newLen));
         //f
         if (newLen >= oldLen) {
             return JSObject::defineOwnProperty(exec, propertyName, newLenDesc, shouldThrow);
         }
         //g
         if (!oldLenDesc.writable()) {
             if (shouldThrow) {
                 throwError(exec, TypeError, "length is not writable");
             }
             return false;
         }
         //h
         bool newWriteable;
         if (!newLenDesc.writableSet() || newLenDesc.writable()) {
             newWriteable = true;
         } else { //i
             if (anyItemHasAttribute(DontDelete)) {
                 newLenDesc.setWritable(false);
             } else {
                 newLenDesc.setWritable(true);
             }
             newWriteable = false;
         }
         //j
         bool succeeded = JSObject::defineOwnProperty(exec, propertyName, newLenDesc, shouldThrow);
         //k
         if (!succeeded) {
             return false;
         }
         //l
         while (newLen < oldLen) {
             --oldLen;
             bool deleteSucceeded = deleteProperty(exec, oldLen); // 3. argument should be false
             if (!deleteSucceeded) {
                 newLenDesc.setValue(jsNumber(oldLen + 1));
                 if (!newWriteable) {
                     newLenDesc.setWritable(false);
                 }
                 JSObject::defineOwnProperty(exec, propertyName, newLenDesc, false);
                 if (shouldThrow) {
                     throwError(exec, TypeError);
                 }
                 return false;
             }
         }
         //m
         if (!newWriteable) {
             PropertyDescriptor writableDesc;
             writableDesc.setWritable(false);
             return JSObject::defineOwnProperty(exec, propertyName, writableDesc, false);
         }
         return true;
     } else if (isArrayIndex) {//Step 4
         //b
         if (index >= oldLen && !oldLenDesc.writable()) {
             if (shouldThrow) {
                 throwError(exec, TypeError);
             }
             return false;
         }
         //c
         bool succeeded = JSObject::defineOwnProperty(exec, propertyName, desc, false);
         //d
         if (!succeeded) {
             if (shouldThrow) {
                 throwError(exec, TypeError);
             }
             return false;
         }
         //e
         if (index >= oldLen) {
             oldLenDesc.setValue(jsNumber(index + 1));
             JSObject::defineOwnProperty(exec, exec->propertyNames().length, oldLenDesc, false);
         }
         return true;
     }
 
     return JSObject::defineOwnProperty(exec, propertyName, desc, shouldThrow);
 }
 
 bool ArrayInstance::getPropertyAttributes(const Identifier &propertyName, unsigned int &attributes) const
 {
     bool isArrayIndex;
     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
 
     if (isArrayIndex) {
         ArrayEntity *ent = getArrayEntity(i);
         if (ent) {
             attributes = ent->attributes;
             return true;
         }
     }
 
     return KJS::JSObject::getPropertyAttributes(propertyName, attributes);
 }
 
 JSValue *ArrayInstance::getDirect(const Identifier &propertyName) const
 {
     bool isArrayIndex;
     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
 
     if (isArrayIndex) {
         ArrayEntity *ent = getArrayEntity(i);
         if (ent) {
             if (ent->value) {
                 return ent->value;
             }
         }
     }
 
     return KJS::JSObject::getDirect(propertyName);
 }
 
 void ArrayInstance::putDirect(unsigned i, JSValue *value, int attributes)
 {
     unsigned length = m_length;
 
     if (i >= length) {
         if (i > maxArrayIndex) {
             KJS::JSObject::putDirect(Identifier::from(i), value, attributes);
             return;
         }
         length = i + 1;
         m_length = length;
     }
 
     ArrayStorage *storage = m_storage;
 
     if (i < m_vectorLength) {
         ArrayEntity *ent = &storage->m_vector[i];
         if (!ent->value && !isExtensible()) {
             return;
         }
         JSValue *&valueSlot = ent->value;
         storage->m_numValuesInVector += !valueSlot;
         valueSlot = value;
         ent->attributes = attributes;
         return;
     }
 
     if (!isExtensible()) {
         return;
     }
 
     SparseArrayValueMap *map = storage->m_sparseValueMap;
     if (i >= sparseArrayCutoff) {
         // If the index is high, go to the map unless we're pretty dense.
         if (!map) {
             map = new SparseArrayValueMap;
             storage->m_sparseValueMap = map;
 
             // If we create a sparse map, we need to ensure that there is at least one spot
             // in the vector map, however, since the sparse map can't put/get key 0.
             // It's safe to do it here, since put(0) will always put it in the vector part,
             // but we have to do it before a get(0) or it will crash
             if (!m_vectorLength) {
                 increaseVectorLength(1);
             }
         }
 
         map->set(i, ArrayEntity(value, attributes));
         return;
     }
 
     // note: an invariant here is that indices < sparseArrayCutoff
     // are always inside the vector portion.
 
     // lowish indices or high density -> 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 the sparse map.
     if (!map || map->isEmpty()) {
         increaseVectorLength(i + 1);
         storage = m_storage;
         ++storage->m_numValuesInVector;
         storage->m_vector[i].value = value;
         storage->m_vector[i].attributes = attributes;
         return;
     }
 
     // Decide just how large we want to make the vector to be.
     unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
     unsigned newVectorLength = increasedVectorLength(i + 1);
 
     // First, count how much stuff we are guaranteed to move over, now
     // that we've decided to at least include i in the vector.
     for (unsigned j = max(m_vectorLength, sparseArrayCutoff); j < newVectorLength; ++j) {
         newNumValuesInVector += map->contains(j);
     }
     if (i >= sparseArrayCutoff) {
         newNumValuesInVector -= map->contains(i);
     }
 
     // Continue increasing the vector portion as long as the things in the map are dense enough
     if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
         unsigned proposedNewNumValuesInVector = newNumValuesInVector;
         while (true) {
             unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
             for (unsigned j = max(newVectorLength, sparseArrayCutoff); j < proposedNewVectorLength; ++j) {
                 proposedNewNumValuesInVector += map->contains(j);
             }
             if (!isDenseEnoughForVector(proposedNewVectorLength, proposedNewNumValuesInVector)) {
                 break;
             }
             newVectorLength = proposedNewVectorLength;
             newNumValuesInVector = proposedNewNumValuesInVector;
         }
     }
 
     storage = static_cast<ArrayStorage *>(fastRealloc(storage, storageSize(newVectorLength)));
 
     unsigned vectorLength = m_vectorLength;
 
     // Special case: if we just added a single value, we don't have to scan the map
     // to see what to remove from it
     if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
         for (unsigned j = vectorLength; j < newVectorLength; ++j) {
             storage->m_vector[j].value = nullptr;
         }
         if (i > sparseArrayCutoff) {
             map->remove(i);
         }
     } else {
         // Move over things from the map to the new array portion
         for (unsigned j = vectorLength; j < max(vectorLength, sparseArrayCutoff); ++j) {
             storage->m_vector[j].value = nullptr;
         }
         for (unsigned j = max(vectorLength, sparseArrayCutoff); j < newVectorLength; ++j) {
             storage->m_vector[j] = map->take(j);
         }
     }
 
     storage->m_vector[i].value = value;
     storage->m_vector[i].attributes = attributes;
 
     m_vectorLength = newVectorLength;
     storage->m_numValuesInVector = newNumValuesInVector;
 
     m_storage = storage;
 }
 
 void ArrayInstance::putDirect(const Identifier &propertyName, JSValue *value, int attr)
 {
     bool isArrayIndex;
     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
 
     if (isArrayIndex) {
         KJS::ArrayInstance::putDirect(i, value, attr);
         return;
     }
 
     KJS::JSObject::putDirect(propertyName, value, attr);
 }
 
 void ArrayInstance::putDirect(const Identifier &propertyName, int value, int attr)
 {
     bool isArrayIndex;
     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
 
     if (isArrayIndex) {
         KJS::ArrayInstance::putDirect(i, jsNumber(value), attr);
         return;
     }
 
     KJS::JSObject::putDirect(propertyName, jsNumber(value), attr);
 }
 
 void ArrayInstance::removeDirect(const Identifier &propertyName)
 {
     bool isArrayIndex;
     unsigned i = propertyName.toArrayIndex(&isArrayIndex);
 
     if (isArrayIndex) {
         ArrayStorage *storage = m_storage;
 
         if (i < m_vectorLength) {
             ArrayEntity *ent = &storage->m_vector[i];
             if (ent->value) {
                 JSValue *&valueSlot = ent->value;
                 bool hadValue = valueSlot;
                 valueSlot = nullptr;
                 storage->m_numValuesInVector -= hadValue;
                 ent->value = nullptr;
                 return;
             }
         }
 
         if (SparseArrayValueMap *map = storage->m_sparseValueMap) {
             SparseArrayValueMap::iterator it = map->find(i);
             if (it != map->end()) {
                 map->remove(it->first);
                 return;
             }
         }
     }
 
     JSObject::removeDirect(Identifier::from(i));
 }
 
 void ArrayInstance::increaseVectorLength(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.
 
     ArrayStorage *storage = m_storage;
 
     unsigned vectorLength = m_vectorLength;
     ASSERT(newLength > vectorLength);
     unsigned newVectorLength = increasedVectorLength(newLength);
 
     storage = static_cast<ArrayStorage *>(fastRealloc(storage, storageSize(newVectorLength)));
     m_vectorLength = newVectorLength;
 
     for (unsigned i = vectorLength; i < newVectorLength; ++i) {
         storage->m_vector[i].value = nullptr;
     }
 
     m_storage = storage;
 }
 
 void ArrayInstance::setLength(unsigned newLength)
 {
     ArrayStorage *storage = m_storage;
 
     unsigned length = m_length;
     unsigned newLenSet = newLength;
 
     if (newLength < length) {
         unsigned usedVectorLength = min(length, m_vectorLength);
         if (usedVectorLength > 0) {
             for (unsigned i = usedVectorLength - 1; i >= newLength && i > 0; --i) {
                 ArrayEntity *ent = &storage->m_vector[i];
                 if (ent->value) {
                     if (ent->attributes & DontDelete) {
                         newLenSet = i + 1;
                         break;
                     }
                     JSValue *&valueSlot = ent->value;
                     bool hadValue = valueSlot;
                     valueSlot = nullptr;
                     ent->value = nullptr;
                     storage->m_numValuesInVector -= hadValue;
                 }
             }
         }
 
         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) {
                     if (it->second.attributes & DontDelete) {
                         newLenSet = it->first + 1;
                     }
                 }
             }
 
             for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
                 if (it->first >= newLenSet) {
                     map->remove(it->first);
                 }
             }
 
             if (map->isEmpty()) {
                 delete map;
                 storage->m_sparseValueMap = nullptr;
             }
         }
     }
 
     m_length = newLenSet;
 }
 
 void ArrayInstance::mark()
 {
     JSObject::mark();
 
     ArrayStorage *storage = m_storage;
 
     unsigned usedVectorLength = min(m_length, m_vectorLength);
     for (unsigned i = 0; i < usedVectorLength; ++i) {
         ArrayEntity *ent = &storage->m_vector[i];
         if (ent->value && !JSValue::marked(ent->value)) {
             JSValue::mark(ent->value);
         }
     }
 
     if (SparseArrayValueMap *map = storage->m_sparseValueMap) {
         SparseArrayValueMap::iterator end = map->end();
         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
             ArrayEntity *ent = &it->second;
             if (!JSValue::marked(ent->value)) {
                 JSValue::mark(ent->value);
             }
         }
     }
 }
 
 static ExecState *execForCompareByStringForQSort;
 
 static int compareByStringForQSort(const void *a, const void *b)
 {
     ExecState *exec = execForCompareByStringForQSort;
 
     const ArrayEntity *va = static_cast<const ArrayEntity *>(a);
     const ArrayEntity *vb = static_cast<const ArrayEntity *>(b);
 
     ASSERT(va->value && !JSValue::isUndefined(va->value));
     ASSERT(vb->value && !JSValue::isUndefined(vb->value));
 
     return compare(JSValue::toString(va->value, exec), JSValue::toString(vb->value, exec));
 }
 
 void ArrayInstance::sort(ExecState *exec)
 {
     unsigned lengthNotIncludingUndefined = compactForSorting();
 
     ExecState *oldExec = execForCompareByStringForQSort;
     execForCompareByStringForQSort = exec;
 
 #if HAVE(MERGESORT)
     // Because mergesort usually does fewer compares, it is faster than qsort here.
     // However, because it requires extra copies of the storage buffer, don't use it for very
     // large arrays.
 
     // FIXME: Since we sort by string value, a fast algorithm might be to convert all the
     // values to string once up front, and then use a radix sort. That would be O(N) rather
     // than O(N log N).
 
     if (lengthNotIncludingUndefined < mergeSortCutoff) {
         // During the sort, we could do a garbage collect, and it's important to still
         // have references to every object in the array for ArrayInstance::mark.
         // The mergesort algorithm does not guarantee this, so we sort a copy rather
         // than the original.
         size_t size = storageSize(m_vectorLength);
         ArrayStorage *copy = static_cast<ArrayStorage *>(fastMalloc(size));
         memcpy(copy, m_storage, size);
         mergesort(copy->m_vector, lengthNotIncludingUndefined, sizeof(ArrayEntity), compareByStringForQSort);
         fastFree(m_storage);
         m_storage = copy;
         execForCompareByStringForQSort = oldExec;
         return;
     }
 #endif
 
     qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(ArrayEntity), compareByStringForQSort);
     execForCompareByStringForQSort = oldExec;
 }
 
 struct CompareWithCompareFunctionArguments {
     CompareWithCompareFunctionArguments(ExecState *e, JSObject *cf)
         : exec(e)
         , compareFunction(cf)
         , globalObject(e->dynamicInterpreter()->globalObject())
     {
     }
 
     ExecState *exec;
     JSObject *compareFunction;
     List arguments;
     JSObject *globalObject;
 };
 
 static CompareWithCompareFunctionArguments *compareWithCompareFunctionArguments;
 
 static int compareWithCompareFunctionForQSort(const void *a, const void *b)
 {
     CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments;
 
     const ArrayEntity *va = static_cast<const ArrayEntity *>(a);
     const ArrayEntity *vb = static_cast<const ArrayEntity *>(b);
 
     ASSERT(va->value && !JSValue::isUndefined(va->value));
     ASSERT(vb->value && !JSValue::isUndefined(vb->value));
 
     args->arguments.clear();
     args->arguments.append(va->value);
     args->arguments.append(vb->value);
     double compareResult = JSValue::toNumber(args->compareFunction->call(args->exec, args->globalObject, args->arguments), args->exec);
     return compareResult < 0 ? -1 : compareResult > 0 ? 1 : 0;
 }
 
 void ArrayInstance::sort(ExecState *exec, JSObject *compareFunction)
 {
     size_t lengthNotIncludingUndefined = compactForSorting();
 
     CompareWithCompareFunctionArguments *oldArgs = compareWithCompareFunctionArguments;
     CompareWithCompareFunctionArguments args(exec, compareFunction);
     compareWithCompareFunctionArguments = &args;
 
 #if HAVE(MERGESORT)
     // Because mergesort usually does fewer compares, it is faster than qsort here.
     // However, because it requires extra copies of the storage buffer, don't use it for very
     // large arrays.
 
     // FIXME: A tree sort using a perfectly balanced tree (e.g. an AVL tree) could do an even
     // better job of minimizing compares.
 
     if (lengthNotIncludingUndefined < mergeSortCutoff) {
         // During the sort, we could do a garbage collect, and it's important to still
         // have references to every object in the array for ArrayInstance::mark.
         // The mergesort algorithm does not guarantee this, so we sort a copy rather
         // than the original.
         size_t size = storageSize(m_vectorLength);
         ArrayStorage *copy = static_cast<ArrayStorage *>(fastMalloc(size));
         memcpy(copy, m_storage, size);
         mergesort(copy->m_vector, lengthNotIncludingUndefined, sizeof(ArrayEntity), compareWithCompareFunctionForQSort);
         fastFree(m_storage);
         m_storage = copy;
         compareWithCompareFunctionArguments = oldArgs;
         return;
     }
 #endif
 
     qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(ArrayEntity), compareWithCompareFunctionForQSort);
     compareWithCompareFunctionArguments = oldArgs;
 }
 
 unsigned ArrayInstance::compactForSorting()
 {
     ArrayStorage *storage = m_storage;
 
     unsigned usedVectorLength = min(m_length, m_vectorLength);
 
     unsigned numDefined = 0;
     unsigned numUndefined = 0;
 
     // This compacts normal values (e.g. not undefined) in a contiguous run
     // at the beginning of the array, and then puts any set undefined values
     // at the end
 
     // count the first contiguous run of defined values in the vector store
     for (; numDefined < usedVectorLength; ++numDefined) {
         ArrayEntity *v = &storage->m_vector[numDefined];
         if (!v->value || JSValue::isUndefined(v->value)) {
             break;
         }
     }
 
     // compact the rest, counting along the way
     for (unsigned i = numDefined; i < usedVectorLength; ++i) {
         ArrayEntity v = storage->m_vector[i];
         if (!v.value || JSValue::isUndefined(v.value)) {
             ++numUndefined;
         } else {
             storage->m_vector[numDefined++] = storage->m_vector[i];
         }
     }
 
     unsigned newUsedVectorLength = numDefined + numUndefined;
 
     if (SparseArrayValueMap *map = storage->m_sparseValueMap) {
         newUsedVectorLength += map->size();
         if (newUsedVectorLength > m_vectorLength) {
             increaseVectorLength(newUsedVectorLength);
             storage = m_storage;
         }
 
         SparseArrayValueMap::iterator end = map->end();
         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
             storage->m_vector[numDefined++] = it->second;
         }
 
         delete map;
         storage->m_sparseValueMap = nullptr;
     }
 
     for (unsigned i = numDefined; i < newUsedVectorLength; ++i) {
         storage->m_vector[i].value = nullptr;
     }
     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i) {
         storage->m_vector[i].value = nullptr;
     }
 
     return numDefined;
 }
 
 bool KJS::ArrayInstance::anyItemHasAttribute(unsigned int attributes) const
 {
     ArrayStorage *storage = m_storage;
 
     unsigned usedVectorLength = min(m_length, m_vectorLength);
     for (unsigned i = 0; i < usedVectorLength; ++i) {
         if (storage->m_vector[i].value && storage->m_vector[i].attributes & attributes) {
             return true;
         }
     }
 
     if (SparseArrayValueMap *map = storage->m_sparseValueMap) {
         SparseArrayValueMap::iterator end = map->end();
         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
             if ((*it).second.attributes & attributes) {
                 return true;
             }
     }
 
     return false;
 }
 
 }