+2007-10-22 Darin Adler <darin@apple.com>
+
+ Reviewed by Maciej.
+
+ - http://bugs.webkit.org/show_bug.cgi?id=15606
+ make cut-off for sparse vs. dense arrays smarter for speed with large arrays
+
+ Makes the morph test in SunSpider 26% faster, and the overall
+ benchmark 3% faster.
+
+ This also fixes some small problems we had with the distinction
+ between nonexistent and undefined values in arrays.
+
+ * kjs/array_instance.h: Tweaked formatting and naming.
+ * kjs/array_instance.cpp: Copied from kjs/array_object.cpp.
+ (KJS::storageSize): Added. Computes the size of the storage given a vector length.
+ (KJS::increasedVectorLength): Added. Implements the rule for resizing the vector.
+ (KJS::isDenseEnoughForVector): Added.
+ (KJS::ArrayInstance::ArrayInstance): Initialize the new fields.
+ (KJS::ArrayInstance::~ArrayInstance): Since m_storage is now never 0, delete it.
+ (KJS::ArrayInstance::getItem): Updated for name changes.
+ (KJS::ArrayInstance::lengthGetter): Ditto.
+ (KJS::ArrayInstance::inlineGetOwnPropertySlot): Added. Allows both versions of
+ getOwnPropertySlot to share more code.
+ (KJS::ArrayInstance::getOwnPropertySlot): Just refactored, no code change.
+ (KJS::ArrayInstance::put): Added logic for extending the vector as long as the
+ array is dense enough. Also keep m_numValuesInVector up to date.
+ (KJS::ArrayInstance::deleteProperty): Added code to keep m_numValuesInVector
+ up to date.
+ (KJS::ArrayInstance::getPropertyNames): Fixed bug where this would omit names
+ for array indices with undefined values.
+ (KJS::ArrayInstance::increaseVectorLength): Renamed from resizeStorage. Also
+ simplified to only handle getting larger.
+ (KJS::ArrayInstance::setLength): Added code to update m_numValuesInVector, to
+ zero out the unused part of the vector and to delete the map if it's no longer
+ needed.
+ (KJS::ArrayInstance::mark): Tweaked formatting.
+ (KJS::compareByStringForQSort): Ditto.
+ (KJS::ArrayInstance::sort): Ditto.
+ (KJS::CompareWithCompareFunctionArguments::CompareWithCompareFunctionArguments):
+ Ditto.
+ (KJS::compareWithCompareFunctionForQSort): Ditto.
+ (KJS::ArrayInstance::compactForSorting): Fixed bug where this would turn
+ undefined values into nonexistent values in some cases.
+
+ * kjs/array_object.h: Removed MAX_ARRAY_INDEX.
+ * kjs/array_object.cpp: Removed ArrayInstance. Moved to a separate file.
+
+ * JavaScriptCore.pri: Added array_instance.cpp.
+ * JavaScriptCore.xcodeproj/project.pbxproj: Ditto.
+ * kjs/AllInOneFile.cpp: Ditto.
+
2007-10-22 Andrew Wellington <proton@wiretapped.net>
Reviewed by Mark Rowe.
kjs/DateMath.cpp \
kjs/JSWrapperObject.cpp \
kjs/PropertyNameArray.cpp \
+ kjs/array_instance.cpp \
kjs/array_object.cpp \
kjs/bool_object.cpp \
kjs/collector.cpp \
<Filter\r
Name="KJS"\r
>\r
+ <File\r
+ RelativePath="..\..\kjs\array_instance.cpp"\r
+ >\r
+ </File>\r
<File\r
RelativePath="..\..\kjs\array_instance.h"\r
>\r
938C4F690CA06BC700D9310A /* ASCIICType.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ASCIICType.h; sourceTree = "<group>"; };
938C4F6B0CA06BCE00D9310A /* DisallowCType.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DisallowCType.h; sourceTree = "<group>"; };
93AA4F770957251F0084B3A7 /* AlwaysInline.h */ = {isa = PBXFileReference; fileEncoding = 4; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = AlwaysInline.h; sourceTree = "<group>"; tabWidth = 8; };
+ 93ADFCE60CCBD7AC00D30B08 /* array_instance.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = array_instance.cpp; sourceTree = "<group>"; };
93B6A0DE0AA64DA40076DE27 /* GetPtr.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = GetPtr.h; sourceTree = "<group>"; };
93E26BC908B1511900F85226 /* pcre_ord2utf8.c */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.c; name = pcre_ord2utf8.c; path = pcre/pcre_ord2utf8.c; sourceTree = "<group>"; tabWidth = 8; };
93E26BD308B1514100F85226 /* pcre_xclass.c */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.c; name = pcre_xclass.c; path = pcre/pcre_xclass.c; sourceTree = "<group>"; tabWidth = 8; };
65400C0F0A69BAF200509887 /* PropertyNameArray.cpp */,
65400C100A69BAF200509887 /* PropertyNameArray.h */,
938772E5038BFE19008635CE /* array_instance.h */,
+ 93ADFCE60CCBD7AC00D30B08 /* array_instance.cpp */,
659126BC0BDD1728001921FB /* AllInOneFile.cpp */,
F692A84D0255597D01FF60F7 /* array_object.cpp */,
F692A84E0255597D01FF60F7 /* array_object.h */,
#include "function.cpp"
#include "debugger.cpp"
+#include "array_instance.cpp"
#include "array_object.cpp"
#include "bool_object.cpp"
#include "collector.cpp"
--- /dev/null
+/*
+ * Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
+ * Copyright (C) 2003, 2007 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 "config.h"
+#include "array_instance.h"
+
+#include "PropertyNameArray.h"
+#include <wtf/Assertions.h>
+
+namespace KJS {
+
+typedef HashMap<unsigned, JSValue*> SparseArrayValueMap;
+
+struct ArrayStorage {
+ unsigned m_numValuesInVector;
+ SparseArrayValueMap* m_sparseValueMap;
+ JSValue* m_vector[1];
+};
+
+// 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", 0, 0, 0};
+
+static inline size_t storageSize(unsigned vectorLength)
+{
+ return sizeof(ArrayStorage) - sizeof(JSValue*) + vectorLength * sizeof(JSValue*);
+}
+
+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));
+
+ Collector::reportExtraMemoryCost(initialCapacity * sizeof(JSValue*));
+}
+
+ArrayInstance::ArrayInstance(JSObject* prototype, const List& list)
+ : JSObject(prototype)
+{
+ unsigned length = list.size();
+
+ m_length = length;
+ m_vectorLength = length;
+
+ ArrayStorage* storage = static_cast<ArrayStorage*>(fastMalloc(storageSize(length)));
+
+ storage->m_numValuesInVector = length;
+ storage->m_sparseValueMap = 0;
+
+ ListIterator it = list.begin();
+ for (unsigned i = 0; i < length; ++i)
+ storage->m_vector[i] = it++;
+
+ 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);
+
+ ArrayStorage* storage = m_storage;
+
+ if (i < m_vectorLength) {
+ JSValue* value = storage->m_vector[i];
+ return value ? value : jsUndefined();
+ }
+
+ SparseArrayValueMap* map = storage->m_sparseValueMap;
+ if (!map)
+ return jsUndefined();
+
+ JSValue* value = map->get(i);
+ return value ? value : 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)
+{
+ ArrayStorage* storage = m_storage;
+
+ if (i >= m_length) {
+ if (i > maxArrayIndex)
+ return getOwnPropertySlot(exec, Identifier::from(i), slot);
+ return false;
+ }
+
+ if (i < m_vectorLength) {
+ JSValue*& valueSlot = storage->m_vector[i];
+ if (valueSlot) {
+ slot.setValueSlot(this, &valueSlot);
+ return true;
+ }
+ } else if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
+ SparseArrayValueMap::iterator it = map->find(i);
+ if (it != map->end()) {
+ slot.setValueSlot(this, &it->second);
+ return true;
+ }
+ }
+
+ return false;
+}
+
+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) {
+ unsigned newLength = value->toUInt32(exec);
+ if (value->toNumber(exec) != static_cast<double>(newLength)) {
+ throwError(exec, RangeError, "Invalid array length.");
+ return;
+ }
+ setLength(newLength);
+ return;
+ }
+
+ JSObject::put(exec, propertyName, value, attributes);
+}
+
+void ArrayInstance::put(ExecState* exec, unsigned i, JSValue* value, int attributes)
+{
+ if (i > maxArrayIndex) {
+ put(exec, Identifier::from(i), value, attributes);
+ return;
+ }
+
+ ArrayStorage* storage = m_storage;
+
+ unsigned length = m_length;
+ if (i >= length) {
+ length = i + 1;
+ m_length = length;
+ }
+
+ if (i < m_vectorLength) {
+ JSValue*& valueSlot = storage->m_vector[i];
+ storage->m_numValuesInVector += !valueSlot;
+ valueSlot = value;
+ return;
+ }
+
+ if (i < sparseArrayCutoff) {
+ increaseVectorLength(i + 1);
+ storage = m_storage;
+ ++storage->m_numValuesInVector;
+ storage->m_vector[i] = value;
+ return;
+ }
+
+ SparseArrayValueMap* map = storage->m_sparseValueMap;
+ if (!map || map->isEmpty()) {
+ if (isDenseEnoughForVector(i + 1, storage->m_numValuesInVector + 1)) {
+ increaseVectorLength(i + 1);
+ storage = m_storage;
+ ++storage->m_numValuesInVector;
+ storage->m_vector[i] = value;
+ return;
+ }
+ if (!map) {
+ map = new SparseArrayValueMap;
+ storage->m_sparseValueMap = map;
+ }
+ map->add(i, value);
+ return;
+ }
+
+ unsigned newNumValuesInVector = storage->m_numValuesInVector + 1;
+ if (!isDenseEnoughForVector(i + 1, newNumValuesInVector)) {
+ map->add(i, value);
+ return;
+ }
+
+ unsigned newVectorLength = increasedVectorLength(i + 1);
+ for (unsigned j = m_vectorLength; j < newVectorLength; ++j)
+ newNumValuesInVector += map->contains(j);
+ newNumValuesInVector -= map->contains(i);
+ if (isDenseEnoughForVector(newVectorLength, newNumValuesInVector)) {
+ unsigned proposedNewNumValuesInVector = newNumValuesInVector;
+ while (true) {
+ unsigned proposedNewVectorLength = increasedVectorLength(newVectorLength + 1);
+ for (unsigned j = newVectorLength; 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;
+ if (newNumValuesInVector == storage->m_numValuesInVector + 1) {
+ for (unsigned j = vectorLength; j < newVectorLength; ++j)
+ storage->m_vector[j] = 0;
+ map->remove(i);
+ } else {
+ for (unsigned j = vectorLength; j < newVectorLength; ++j) {
+ SparseArrayValueMap::iterator it = map->find(j);
+ if (it == map->end())
+ storage->m_vector[j] = 0;
+ else {
+ storage->m_vector[j] = it->second;
+ map->remove(it);
+ }
+ }
+ }
+
+ storage->m_vector[i] = value;
+
+ m_vectorLength = newVectorLength;
+ storage->m_numValuesInVector = newNumValuesInVector;
+}
+
+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) {
+ JSValue*& valueSlot = storage->m_vector[i];
+ bool hadValue = valueSlot;
+ valueSlot = 0;
+ storage->m_numValuesInVector -= hadValue;
+ return hadValue;
+ }
+
+ if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
+ SparseArrayValueMap::iterator it = map->find(i);
+ if (it != map->end()) {
+ map->remove(it);
+ return true;
+ }
+ }
+
+ if (i > maxArrayIndex)
+ return deleteProperty(exec, Identifier::from(i));
+
+ return false;
+}
+
+void ArrayInstance::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
+{
+ // 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])
+ 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)
+ propertyNames.add(Identifier::from(it->first));
+ }
+
+ JSObject::getPropertyNames(exec, propertyNames);
+}
+
+void ArrayInstance::increaseVectorLength(unsigned newLength)
+{
+ 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] = 0;
+
+ m_storage = storage;
+}
+
+void ArrayInstance::setLength(unsigned newLength)
+{
+ ArrayStorage* storage = m_storage;
+
+ unsigned length = m_length;
+
+ if (newLength < length) {
+ unsigned usedVectorLength = min(length, m_vectorLength);
+ for (unsigned i = newLength; i < usedVectorLength; ++i) {
+ JSValue*& valueSlot = storage->m_vector[i];
+ bool hadValue = valueSlot;
+ valueSlot = 0;
+ 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)
+ map->remove(it->first);
+ }
+ if (map->isEmpty()) {
+ delete map;
+ storage->m_sparseValueMap = 0;
+ }
+ }
+ }
+
+ m_length = newLength;
+}
+
+void ArrayInstance::mark()
+{
+ JSObject::mark();
+
+ ArrayStorage* storage = m_storage;
+
+ unsigned usedVectorLength = min(m_length, m_vectorLength);
+ for (unsigned i = 0; i < usedVectorLength; ++i) {
+ JSValue* value = storage->m_vector[i];
+ if (value && !value->marked())
+ value->mark();
+ }
+
+ if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
+ SparseArrayValueMap copy = *map;
+ SparseArrayValueMap::iterator end = copy.end();
+ for (SparseArrayValueMap::iterator it = copy.begin(); it != end; ++it) {
+ JSValue* value = it->second;
+ if (!value->marked())
+ value->mark();
+ }
+ }
+}
+
+static ExecState* execForCompareByStringForQSort = 0;
+
+static int compareByStringForQSort(const void* a, const void* b)
+{
+ ExecState* exec = execForCompareByStringForQSort;
+
+ JSValue* va = *static_cast<JSValue* const*>(a);
+ JSValue* vb = *static_cast<JSValue* const*>(b);
+ ASSERT(!va->isUndefined());
+ ASSERT(!vb->isUndefined());
+
+ return compare(va->toString(exec), vb->toString(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(JSValue*), compareByStringForQSort);
+ fastFree(m_storage);
+ m_storage = copy;
+ execForCompareByStringForQSort = oldExec;
+ return;
+ }
+#endif
+
+ qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), 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 = 0;
+
+static int compareWithCompareFunctionForQSort(const void* a, const void* b)
+{
+ CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments;
+
+ JSValue* va = *static_cast<JSValue* const*>(a);
+ JSValue* vb = *static_cast<JSValue* const*>(b);
+ ASSERT(!va->isUndefined());
+ ASSERT(!vb->isUndefined());
+
+ args->arguments.clear();
+ args->arguments.append(va);
+ args->arguments.append(vb);
+ double compareResult = args->compareFunction->call
+ (args->exec, args->globalObject, args->arguments)->toNumber(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(JSValue*), compareWithCompareFunctionForQSort);
+ fastFree(m_storage);
+ m_storage = copy;
+ compareWithCompareFunctionArguments = oldArgs;
+ return;
+ }
+#endif
+
+ qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
+ compareWithCompareFunctionArguments = oldArgs;
+}
+
+unsigned ArrayInstance::compactForSorting()
+{
+ ArrayStorage* storage = m_storage;
+
+ unsigned usedVectorLength = min(m_length, m_vectorLength);
+
+ unsigned numDefined = 0;
+ unsigned numUndefined = 0;
+
+ for (; numDefined < usedVectorLength; ++numDefined) {
+ JSValue* v = storage->m_vector[numDefined];
+ if (!v || v->isUndefined())
+ break;
+ }
+ for (unsigned i = numDefined; i < usedVectorLength; ++i) {
+ if (JSValue* v = storage->m_vector[i]) {
+ if (v->isUndefined())
+ ++numUndefined;
+ else
+ storage->m_vector[numDefined++] = v;
+ }
+ }
+
+ unsigned newUsedVectorLength = numDefined + numUndefined;
+
+ if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
+ newUsedVectorLength += map->size();
+ if (newUsedVectorLength > 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 = 0;
+ }
+
+ for (unsigned i = numDefined; i < newUsedVectorLength; ++i)
+ storage->m_vector[i] = jsUndefined();
+ for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
+ storage->m_vector[i] = 0;
+
+ return numDefined;
+}
+
+}
// -*- c-basic-offset: 2 -*-
/*
- * This file is part of the KDE libraries
* Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
* Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
*
namespace KJS {
+ struct ArrayStorage;
+
class ArrayInstance : public JSObject {
public:
- ArrayInstance(JSObject *proto, unsigned initialLength);
- ArrayInstance(JSObject *proto, const List &initialValues);
+ ArrayInstance(JSObject* prototype, unsigned initialLength);
+ ArrayInstance(JSObject* prototype, const List& initialValues);
~ArrayInstance();
- virtual bool getOwnPropertySlot(ExecState *, const Identifier&, PropertySlot&);
- virtual bool getOwnPropertySlot(ExecState *, unsigned, PropertySlot&);
- virtual void put(ExecState *exec, const Identifier &propertyName, JSValue *value, int attr = None);
- virtual void put(ExecState *exec, unsigned propertyName, JSValue *value, int attr = None);
- virtual bool deleteProperty(ExecState *exec, const Identifier &propertyName);
- virtual bool deleteProperty(ExecState *exec, unsigned propertyName);
+ virtual bool getOwnPropertySlot(ExecState*, const Identifier& propertyName, PropertySlot&);
+ virtual bool getOwnPropertySlot(ExecState*, unsigned propertyName, PropertySlot&);
+ virtual void put(ExecState*, const Identifier& propertyName, JSValue*, int attributes = None);
+ virtual void put(ExecState*, unsigned propertyName, JSValue*, int attributes = None);
+ virtual bool deleteProperty(ExecState *, const Identifier& propertyName);
+ virtual bool deleteProperty(ExecState *, unsigned propertyName);
virtual void getPropertyNames(ExecState*, PropertyNameArray&);
virtual void mark();
- virtual const ClassInfo *classInfo() const { return &info; }
+ virtual const ClassInfo* classInfo() const { return &info; }
static const ClassInfo info;
-
- unsigned getLength() const { return length; }
+
+ unsigned getLength() const { return m_length; }
JSValue* getItem(unsigned) const;
-
- void sort(ExecState *exec);
- void sort(ExecState *exec, JSObject *compareFunction);
-
+
+ void sort(ExecState*);
+ void sort(ExecState*, JSObject* compareFunction);
+
private:
- static JSValue *lengthGetter(ExecState *, JSObject *, const Identifier&, const PropertySlot&);
+ static JSValue* lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot&);
+ bool inlineGetOwnPropertySlot(ExecState*, unsigned propertyName, PropertySlot&);
- void setLength(unsigned newLength);
+ void setLength(unsigned);
+ void increaseVectorLength(unsigned newLength);
- unsigned compactForSorting();
-
- void resizeStorage(unsigned);
-
- // store capacity in extra space at the beginning of the storage array to save space
- size_t capacity() { return storage ? reinterpret_cast<size_t>(storage[-1]) : 0; }
+ unsigned compactForSorting();
- unsigned length;
- unsigned storageLength;
- JSValue **storage;
+ unsigned m_length;
+ unsigned m_vectorLength;
+ ArrayStorage* m_storage;
};
} // namespace KJS
// -*- c-basic-offset: 2 -*-
/*
- * This file is part of the KDE libraries
* Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
* Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
* Copyright (C) 2003 Peter Kelly (pmk@post.com)
#include "array_object.h"
#include "array_object.lut.h"
-#include "PropertyNameArray.h"
#include "error_object.h"
#include "lookup.h"
#include "operations.h"
#include <wtf/Assertions.h>
#include <wtf/HashSet.h>
-
namespace KJS {
-typedef HashMap<unsigned, JSValue*> OverflowMap;
-
-static inline OverflowMap* overflowMap(JSValue** storage)
-{
- return storage ? reinterpret_cast<OverflowMap*>(storage[-2]) : 0;
-}
-
-// ------------------------------ ArrayInstance -----------------------------
-
-const unsigned sparseArrayCutoff = 10000;
-
-const ClassInfo ArrayInstance::info = {"Array", 0, 0, 0};
-
-static inline JSValue** allocateStorage(size_t capacity)
-{
- if (capacity == 0)
- return 0;
-
- // store capacity and overflow map in extra space before the beginning of the storage array to save space
- JSValue** storage = static_cast<JSValue**>(fastCalloc(capacity + 2, sizeof(JSValue *))) + 2;
- storage[-1] = reinterpret_cast<JSValue*>(capacity);
- return storage;
-}
-
-static inline void reallocateStorage(JSValue**& storage, size_t newCapacity)
-{
- if (!storage) {
- storage = allocateStorage(newCapacity);
- return;
- }
-
- // store capacity and overflow map in extra space before the beginning of the storage array to save space
- storage = static_cast<JSValue**>(fastRealloc(storage - 2, (newCapacity + 2) * sizeof (JSValue*))) + 2;
- storage[-1] = reinterpret_cast<JSValue*>(newCapacity);
-}
-
-static inline void freeStorage(JSValue** storage)
-{
- if (storage)
- fastFree(storage - 2);
-}
-
-ArrayInstance::ArrayInstance(JSObject *proto, unsigned initialLength)
- : JSObject(proto)
- , length(initialLength)
- , storageLength(initialLength < sparseArrayCutoff ? initialLength : 0)
- , storage(allocateStorage(storageLength))
-{
- Collector::reportExtraMemoryCost(storageLength * sizeof(JSValue*));
-}
-
-ArrayInstance::ArrayInstance(JSObject *proto, const List &list)
- : JSObject(proto)
- , length(list.size())
- , storageLength(length)
- , storage(allocateStorage(storageLength))
-{
- ListIterator it = list.begin();
- unsigned l = length;
- for (unsigned i = 0; i < l; ++i)
- storage[i] = it++;
- // 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()
-{
- if (storage) {
- delete reinterpret_cast<OverflowMap*>(storage[-2]);
- freeStorage(storage);
- }
-}
-
-JSValue* ArrayInstance::getItem(unsigned i) const
-{
- if (i < storageLength) {
- JSValue* value = storage[i];
- return value ? value : jsUndefined();
- }
-
- const OverflowMap* overflow = overflowMap(storage);
- if (!overflow)
- return jsUndefined();
-
- JSValue* value = overflow->get(i);
- return value ? value : jsUndefined();
-}
-
-JSValue *ArrayInstance::lengthGetter(ExecState*, JSObject*, const Identifier&, const PropertySlot& slot)
-{
- return jsNumber(static_cast<ArrayInstance *>(slot.slotBase())->length);
-}
-
-bool ArrayInstance::getOwnPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
-{
- if (propertyName == exec->propertyNames().length) {
- slot.setCustom(this, lengthGetter);
- return true;
- }
-
- bool ok;
- unsigned index = propertyName.toArrayIndex(&ok);
- if (!ok)
- return JSObject::getOwnPropertySlot(exec, propertyName, slot);
-
- if (index < storageLength) {
- JSValue *v = storage[index];
- if (!v)
- return false;
- slot.setValueSlot(this, &storage[index]);
- return true;
- }
- if (index > MAX_ARRAY_INDEX)
- return JSObject::getOwnPropertySlot(exec, propertyName, slot);
- OverflowMap* overflow = overflowMap(storage);
- if (!overflow)
- return false;
- OverflowMap::iterator it = overflow->find(index);
- if (it == overflow->end())
- return false;
- slot.setValueSlot(this, &it->second);
- return true;
-}
-
-bool ArrayInstance::getOwnPropertySlot(ExecState *exec, unsigned index, PropertySlot& slot)
-{
- if (index < storageLength) {
- JSValue *v = storage[index];
- if (!v)
- return false;
- slot.setValueSlot(this, &storage[index]);
- return true;
- }
- if (index > MAX_ARRAY_INDEX)
- return getOwnPropertySlot(exec, Identifier::from(index), slot);
- OverflowMap* overflow = overflowMap(storage);
- if (!overflow)
- return false;
- OverflowMap::iterator it = overflow->find(index);
- if (it == overflow->end())
- return false;
- slot.setValueSlot(this, &it->second);
- return true;
-}
-
-// Special implementation of [[Put]] - see ECMA 15.4.5.1
-void ArrayInstance::put(ExecState* exec, const Identifier& propertyName, JSValue* value, int attr)
-{
- if (propertyName == exec->propertyNames().length) {
- unsigned int newLen = value->toUInt32(exec);
- if (value->toNumber(exec) != double(newLen)) {
- throwError(exec, RangeError, "Invalid array length.");
- return;
- }
- setLength(newLen);
- return;
- }
-
- bool ok;
- unsigned index = propertyName.toArrayIndex(&ok);
- if (ok) {
- put(exec, index, value, attr);
- return;
- }
-
- JSObject::put(exec, propertyName, value, attr);
-}
-
-void ArrayInstance::put(ExecState *exec, unsigned index, JSValue *value, int attr)
-{
- // 0xFFFFFFFF is a bit weird --- it should be treated as a non-array index, even when it's a string
- if (index > MAX_ARRAY_INDEX) {
- put(exec, Identifier::from(index), value, attr);
- return;
- }
-
- if (index < sparseArrayCutoff && index >= storageLength)
- resizeStorage(index + 1);
-
- if (index >= length)
- length = index + 1;
-
- if (index < storageLength) {
- storage[index] = value;
- return;
- }
-
- OverflowMap* overflow = overflowMap(storage);
- if (!overflow) {
- overflow = new OverflowMap;
- if (!storage)
- storage = allocateStorage(1);
- storage[-2] = reinterpret_cast<JSValue*>(overflow);
- }
- overflow->add(index, value);
-}
-
-bool ArrayInstance::deleteProperty(ExecState* exec, const Identifier &propertyName)
-{
- if (propertyName == exec->propertyNames().length)
- return false;
-
- bool ok;
- uint32_t index = propertyName.toArrayIndex(&ok);
- if (ok) {
- if (index >= length)
- return true;
- if (index < storageLength) {
- storage[index] = 0;
- return true;
- }
- if (OverflowMap* overflow = overflowMap(storage)) {
- OverflowMap::iterator it = overflow->find(index);
- if (it == overflow->end())
- return false;
- overflow->remove(it);
- return true;
- }
- return false;
- }
-
- return JSObject::deleteProperty(exec, propertyName);
-}
-
-bool ArrayInstance::deleteProperty(ExecState *exec, unsigned index)
-{
- if (index > MAX_ARRAY_INDEX)
- return deleteProperty(exec, Identifier::from(index));
-
- if (index >= length)
- return true;
- if (index < storageLength) {
- storage[index] = 0;
- return true;
- }
- OverflowMap* overflow = overflowMap(storage);
- if (!overflow)
- return false;
- OverflowMap::iterator it = overflow->find(index);
- if (it == overflow->end())
- return false;
- overflow->remove(it);
- return true;
-}
-
-void ArrayInstance::getPropertyNames(ExecState* exec, PropertyNameArray& propertyNames)
-{
- // avoid fetching this every time through the loop
- JSValue* undefined = jsUndefined();
-
- for (unsigned i = 0; i < storageLength; ++i) {
- JSValue* value = storage[i];
- if (value && value != undefined)
- propertyNames.add(Identifier::from(i));
- }
-
- OverflowMap* overflow = overflowMap(storage);
- if (overflow) {
- OverflowMap::iterator end = overflow->end();
- for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
- JSValue* value = it->second;
- if (value && value != undefined)
- propertyNames.add(Identifier::from(it->first));
- }
- }
-
- JSObject::getPropertyNames(exec, propertyNames);
-}
-
-void ArrayInstance::resizeStorage(unsigned newLength)
-{
- if (newLength < storageLength) {
- memset(storage + newLength, 0, sizeof(JSValue *) * (storageLength - newLength));
- }
- size_t cap = capacity();
- if (newLength > cap) {
- unsigned newCapacity;
- if (newLength > sparseArrayCutoff) {
- newCapacity = newLength;
- } else {
- newCapacity = (newLength * 3 + 1) / 2;
- if (newCapacity > sparseArrayCutoff) {
- newCapacity = sparseArrayCutoff;
- }
- }
-
- reallocateStorage(storage, newCapacity);
- memset(storage + cap, 0, sizeof(JSValue*) * (newCapacity - cap));
- }
- storageLength = newLength;
-}
-
-void ArrayInstance::setLength(unsigned newLength)
-{
- if (newLength <= storageLength)
- resizeStorage(newLength);
-
- if (newLength < length) {
- if (OverflowMap* overflow = overflowMap(storage)) {
- OverflowMap copy = *overflow;
- OverflowMap::iterator end = copy.end();
- for (OverflowMap::iterator it = copy.begin(); it != end; ++it) {
- if (it->first >= newLength)
- overflow->remove(it->first);
- }
- }
- }
-
- length = newLength;
-}
-
-void ArrayInstance::mark()
-{
- JSObject::mark();
- unsigned l = storageLength;
- for (unsigned i = 0; i < l; ++i) {
- JSValue* imp = storage[i];
- if (imp && !imp->marked())
- imp->mark();
- }
- if (OverflowMap* overflow = overflowMap(storage)) {
- OverflowMap::iterator end = overflow->end();
- for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
- JSValue* value = it->second;
- if (value && !value->marked())
- value->mark();
- }
- }
-}
-
-static ExecState* execForCompareByStringForQSort = 0;
-
-static int compareByStringForQSort(const void *a, const void *b)
-{
- ExecState *exec = execForCompareByStringForQSort;
- JSValue *va = *(JSValue **)a;
- JSValue *vb = *(JSValue **)b;
- ASSERT(!va->isUndefined());
- ASSERT(!vb->isUndefined());
- return compare(va->toString(exec), vb->toString(exec));
-}
-
-void ArrayInstance::sort(ExecState* exec)
-{
- size_t lengthNotIncludingUndefined = compactForSorting();
-
- ExecState* oldExec = execForCompareByStringForQSort;
- execForCompareByStringForQSort = exec;
-#if HAVE(MERGESORT)
- // mergesort usually does fewer compares, so it is actually faster than qsort for JS sorts.
- // however, becuase it requires extra copies of the storage buffer, don't use it for very
- // large arrays
- // FIXME: for sorting by string value, the fastest thing would actually 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 < sparseArrayCutoff) {
- JSValue** storageCopy = allocateStorage(capacity());
- memcpy(storageCopy, storage, capacity() * sizeof(JSValue*));
- mergesort(storageCopy, lengthNotIncludingUndefined, sizeof(JSValue *), compareByStringForQSort);
- freeStorage(storage);
- storage = storageCopy;
- execForCompareByStringForQSort = oldExec;
- return;
- }
-#endif
-
- qsort(storage, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
- execForCompareByStringForQSort = oldExec;
-}
-
-struct CompareWithCompareFunctionArguments {
- CompareWithCompareFunctionArguments(ExecState *e, JSObject *cf)
- : exec(e)
- , compareFunction(cf)
- , globalObject(e->dynamicInterpreter()->globalObject())
- {
- arguments.append(jsUndefined());
- arguments.append(jsUndefined());
- }
-
- ExecState *exec;
- JSObject *compareFunction;
- List arguments;
- JSObject *globalObject;
-};
-
-static CompareWithCompareFunctionArguments* compareWithCompareFunctionArguments = 0;
-
-static int compareWithCompareFunctionForQSort(const void *a, const void *b)
-{
- CompareWithCompareFunctionArguments *args = compareWithCompareFunctionArguments;
-
- JSValue *va = *(JSValue **)a;
- JSValue *vb = *(JSValue **)b;
- ASSERT(!va->isUndefined());
- ASSERT(!vb->isUndefined());
-
- args->arguments.clear();
- args->arguments.append(va);
- args->arguments.append(vb);
- double compareResult = args->compareFunction->call
- (args->exec, args->globalObject, args->arguments)->toNumber(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)
- // mergesort usually does fewer compares, so it is actually faster than qsort for JS sorts.
- // however, becuase 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 < sparseArrayCutoff) {
- JSValue** storageCopy = allocateStorage(capacity());
- memcpy(storageCopy, storage, capacity() * sizeof(JSValue*));
- mergesort(storageCopy, lengthNotIncludingUndefined, sizeof(JSValue *), compareWithCompareFunctionForQSort);
- freeStorage(storage);
- storage = storageCopy;
- compareWithCompareFunctionArguments = oldArgs;
- return;
- }
-#endif
- qsort(storage, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
- compareWithCompareFunctionArguments = oldArgs;
-}
-
-unsigned ArrayInstance::compactForSorting()
-{
- JSValue *undefined = jsUndefined();
-
- unsigned o = 0;
-
- for (unsigned i = 0; i != storageLength; ++i) {
- JSValue *v = storage[i];
- if (v && v != undefined) {
- if (o != i)
- storage[o] = v;
- o++;
- }
- }
-
- unsigned newLength = o;
-
- if (OverflowMap* overflow = overflowMap(storage)) {
- OverflowMap::iterator end = overflow->end();
- for (OverflowMap::iterator it = overflow->begin(); it != end; ++it)
- newLength += it->second != undefined;
-
- if (newLength > storageLength)
- resizeStorage(newLength);
-
- for (OverflowMap::iterator it = overflow->begin(); it != end; ++it) {
- JSValue* v = it->second;
- if (v != undefined) {
- storage[o] = v;
- o++;
- }
- }
- delete overflow;
- storage[-2] = 0;
- }
-
- if (newLength != storageLength)
- memset(storage + o, 0, sizeof(JSValue *) * (storageLength - o));
-
- return o;
-}
-
// ------------------------------ ArrayPrototype ----------------------------
const ClassInfo ArrayPrototype::info = {"Array", &ArrayInstance::info, &arrayTable, 0};
int id;
};
- const unsigned MAX_ARRAY_INDEX = 0xFFFFFFFEu;
-
class ArrayObjectImp : public InternalFunctionImp {
public:
ArrayObjectImp(ExecState *exec,
+2007-10-22 Darin Adler <darin@apple.com>
+
+ * fast/js/kde/resources/Array.js: Added tests to cover missing value behavior
+ (not the same as undefined values in arrays). This matches the ECMA JavaScript
+ specification, but doesn't exactly match Firefox.
+ * fast/js/kde/Array-expected.txt: Updated with results.
+
2007-10-21 Mark Rowe <mrowe@apple.com>
Reviewed by Mitz.
2007-10-21 Nikolas Zimmermann <zimmermann@kde.org>
- Not reviewed.
-
Forgot to land the new computed style results in fast/css - after the addition of glyph-orientation-*.
* fast/css/computed-style-expected.txt:
PASS ['a'].length is 1
PASS ['a'][0] is 'a'
PASS ['a',,'c'][2] is 'c'
+PASS ['a',undefined,'c'][1] is undefined
+PASS ['a',,'c'][1] is undefined
+PASS 1 in ['a',,'c'] is false
+PASS 1 in ['a',undefined,'c'] is true
+PASS 1 in arrayWithDeletion is false
PASS forInSum([]) is ''
PASS forInSum(Array()) is ''
PASS forInSum(Array('a')) is 'a'
+PASS forInSum([,undefined,'x','aa']) is 'undefinedxaa'
PASS forInSum(a0) is ''
PASS forInSum(a1) is 'a'
PASS String([].sort()) is ''
PASS String([3,1,'2'].sort()) is '1,2,3'
PASS String([,'x','aa'].sort()) is 'aa,x,'
+PASS String([,undefined,'x','aa'].sort()) is 'aa,x,,'
+PASS 2 in [,undefined,'x','aa'].sort() is true
+PASS 3 in [,undefined,'x','aa'].sort() is false
PASS var a = ['aa', 'b', 'cccc', 'ddd']; String(a.sort(comp)) is 'b,aa,ddd,cccc'
PASS [0, Infinity].sort(function(a, b) { return a - b }).toString() is '0,Infinity'
PASS [].unshift('a') is 1
shouldBe("['a'].length", "1");
shouldBe("['a'][0]", "'a'");
shouldBe("['a',,'c'][2]", "'c'");
+shouldBe("['a',undefined,'c'][1]", "undefined");
+shouldBe("['a',,'c'][1]", "undefined");
+shouldBe("1 in ['a',,'c']", "false");
+shouldBe("1 in ['a',undefined,'c']", "true");
+
+var arrayWithDeletion = ['a','b','c'];
+delete arrayWithDeletion[1];
+shouldBe("1 in arrayWithDeletion", "false");
function forInSum(_a) {
var s = '';
shouldBe("forInSum([])", "''");
shouldBe("forInSum(Array())", "''");
shouldBe("forInSum(Array('a'))", "'a'");
+shouldBe("forInSum([,undefined,'x','aa'])", "'undefinedxaa'");
var a0 = [];
shouldBe("forInSum(a0)", "''");
shouldBe("String([].sort())", "''")
shouldBe("String([3,1,'2'].sort())", "'1,2,3'");
-shouldBe("String([,'x','aa'].sort())", "'aa,x,'"); // don't assume 'x'>undefined !
+shouldBe("String([,'x','aa'].sort())", "'aa,x,'");
+shouldBe("String([,undefined,'x','aa'].sort())", "'aa,x,,'");
+shouldBe("2 in [,undefined,'x','aa'].sort()", "true");
+shouldBe("3 in [,undefined,'x','aa'].sort()", "false");
// sort by length
function comp(a, b) {
git://git.webkit.org / WebKit-https.git / commitdiff