Changeset 34496 in webkit for trunk/JavaScriptCore/kjs/array_instance.cpp

Timestamp:

Jun 11, 2008, 12:37:44 PM (17 years ago)

Author:

Darin Adler

Message:

2008-06-11 Darin Adler <Darin Adler>

Reviewed by Alexey.

• fix ​https://bugs.webkit.org/show_bug.cgi?id=19442 JavaScript array implementation doesn't maintain m_numValuesInVector when sorting

• kjs/array_instance.cpp: (KJS::ArrayInstance::checkConsistency): Added. Empty inline version for when consistency checks are turned off. (KJS::ArrayInstance::ArrayInstance): Check consistency after construction. (KJS::ArrayInstance::~ArrayInstance): Check consistency before destruction. (KJS::ArrayInstance::put): Check consistency before and after. (KJS::ArrayInstance::deleteProperty): Ditto. (KJS::ArrayInstance::setLength): Ditto. (KJS::compareByStringPairForQSort): Use typedef for clarity. (KJS::ArrayInstance::sort): Check consistency before and after. Also broke the loop to set up sorting into two separate passes. Added FIXMEs about various exception safety issues. Added code to set m_numValuesInVector after sorting. (KJS::ArrayInstance::compactForSorting): Ditto.

• kjs/array_instance.h: Added a definition of an enum for the types of consistency check and a declaration of the consistency checking function.

File:

• trunk/JavaScriptCore/kjs/array_instance.cpp (modified) (26 diffs)

trunk/JavaScriptCore/kjs/array_instance.cpp

@@ -28 +28 @@
 #include <wtf/AVLTree.h>
 
+#define CHECK_ARRAY_CONSISTENCY 0
+
 using namespace std;
 
@@ -41 +43 @@
 };
 
-// 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer
+// 0xFFFFFFFF is a bit weird -- is not an array index even though it's an integer.
 static const unsigned maxArrayIndex = 0xFFFFFFFEU;
 
@@ -70 +72 @@
 }
 
+#if !CHECK_ARRAY_CONSISTENCY
+
+inline void ArrayInstance::checkConsistency(ConsistencyCheckType)
+{
+}
+
+#endif
+
 ArrayInstance::ArrayInstance(JSObject* prototype, unsigned initialLength)
     : JSObject(prototype)
@@ -80 +90 @@
 
     Collector::reportExtraMemoryCost(initialCapacity * sizeof(JSValue*));
+
+    checkConsistency();
 }
 
@@ -104 +116 @@
     // 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.
+
+    checkConsistency();
 }
 
 ArrayInstance::~ArrayInstance()
 {
+    checkConsistency(DestructorConsistencyCheck);
+
     delete m_storage->m_sparseValueMap;
     fastFree(m_storage);
@@ -210 +226 @@
 void ArrayInstance::put(ExecState* exec, unsigned i, JSValue* value)
 {
+    checkConsistency();
+
     unsigned length = m_length;
     if (i >= length) {
@@ -226 +244 @@
         storage->m_numValuesInVector += !valueSlot;
         valueSlot = value;
+        checkConsistency();
         return;
     }
@@ -251 +270 @@
         ++storage->m_numValuesInVector;
         storage->m_vector[i] = value;
+        checkConsistency();
         return;
     }
@@ -295 +315 @@
 
     m_storage = storage;
+
+    checkConsistency();
 }
 
@@ -312 +334 @@
 bool ArrayInstance::deleteProperty(ExecState* exec, unsigned i)
 {
+    checkConsistency();
+
     ArrayStorage* storage = m_storage;
 
@@ -319 +343 @@
         valueSlot = 0;
         storage->m_numValuesInVector -= hadValue;
+        checkConsistency();
         return hadValue;
     }
@@ -327 +352 @@
             if (it != map->end()) {
                 map->remove(it);
+                checkConsistency();
                 return true;
             }
@@ -332 +358 @@
     }
 
+    checkConsistency();
+
     if (i > maxArrayIndex)
         return deleteProperty(exec, Identifier::from(i));
@@ -341 +369 @@
 {
     // FIXME: Filling PropertyNameArray with an identifier for every integer
-    // is incredibly inefficient for large arrays. We need a different approach.
+    // is incredibly inefficient for large arrays. We need a different approach,
+    // which almost certainly means a different structure for PropertyNameArray.
 
     ArrayStorage* storage = m_storage;
@@ -386 +415 @@
 void ArrayInstance::setLength(unsigned newLength)
 {
+    checkConsistency();
+
     ArrayStorage* storage = m_storage;
 
@@ -414 +445 @@
 
     m_length = newLength;
+
+    checkConsistency();
 }
 
@@ -439 +472 @@
 }
 
+typedef std::pair<JSValue*, UString> ArrayQSortPair;
+
 static int compareByStringPairForQSort(const void* a, const void* b)
 {
-    const std::pair<JSValue*, UString>* va = static_cast<const std::pair<JSValue*, UString>*>(a);
-    const std::pair<JSValue*, UString>* vb = static_cast<const std::pair<JSValue*, UString>*>(b);
+    const ArrayQSortPair* va = static_cast<const ArrayQSortPair*>(a);
+    const ArrayQSortPair* vb = static_cast<const ArrayQSortPair*>(b);
     return compare(va->second, vb->second);
 }
@@ -462 +497 @@
     // random or otherwise changing results, effectively making compare function inconsistent.
 
-    Vector<std::pair<JSValue*, UString> > values(lengthNotIncludingUndefined);
+    Vector<ArrayQSortPair> values(lengthNotIncludingUndefined);
     if (!values.begin()) {
         exec->setException(Error::create(exec, GeneralError, "Out of memory"));
@@ -472 +507 @@
         ASSERT(!value->isUndefined());
         values[i].first = value;
-        values[i].second = value->toString(exec);
-    }
+    }
+
+    // FIXME: While calling these toString functions, the array could be mutated.
+    // In that case, objects pointed to by values in this vector might get garbage-collected!
+
+    // FIXME: The following loop continues to call toString on subsequent values even after
+    // a toString call raises an exception.
+
+    for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
+        values[i].second = values[i].first->toString(exec);
 
     if (exec->hadException())
@@ -482 +525 @@
 
 #if HAVE(MERGESORT)
-    mergesort(values.begin(), values.size(), sizeof(std::pair<JSValue*, UString>), compareByStringPairForQSort);
+    mergesort(values.begin(), values.size(), sizeof(ArrayQSortPair), compareByStringPairForQSort);
 #else
-    // FIXME: QSort may not be stable in some implementations. ECMAScript-262 does not require this, but in practice, browsers perform stable sort.
-    qsort(values.begin(), values.size(), sizeof(std::pair<JSValue*, UString>), compareByStringPairForQSort);
+    // 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(ArrayQSortPair), compareByStringPairForQSort);
 #endif
+
+    // FIXME: If the toString function changed the length of the array, this might be
+    // modifying the vector incorrectly.
 
     for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
         m_storage->m_vector[i] = values[i].first;
+
+    checkConsistency(SortConsistencyCheck);
 }
 
@@ -559 +608 @@
 void ArrayInstance::sort(ExecState* exec, JSObject* compareFunction)
 {
+    checkConsistency();
+
+    // 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.
@@ -580 +633 @@
         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.
 
     unsigned numDefined = 0;
@@ -628 +684 @@
     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.
+
     // Copy the values back into m_storage.
     AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
@@ -643 +702 @@
     for (unsigned i = newUsedVectorLength; i < usedVectorLength; ++i)
         m_storage->m_vector[i] = 0;
+
+    m_storage->m_numValuesInVector = newUsedVectorLength;
+
+    checkConsistency(SortConsistencyCheck);
 }
 
 unsigned ArrayInstance::compactForSorting()
 {
+    checkConsistency();
+
     ArrayStorage* storage = m_storage;
 
@@ -691 +756 @@
         storage->m_vector[i] = 0;
 
+    storage->m_numValuesInVector = newUsedVectorLength;
+
+    checkConsistency(SortConsistencyCheck);
+
     return numDefined;
 }
@@ -704 +773 @@
 }
 
-}
+#if CHECK_ARRAY_CONSISTENCY
+
+void ArrayInstance::checkConsistency(ConsistencyCheckType type)
+{
+    ASSERT(m_storage);
+    if (type == SortConsistencyCheck)
+        ASSERT(!m_storage->m_sparseValueMap);
+
+    unsigned numValuesInVector = 0;
+    for (unsigned i = 0; i < m_vectorLength; ++i) {
+        if (JSValue* value = m_storage->m_vector[i]) {
+            ASSERT(i < m_length);
+            if (type != DestructorConsistencyCheck)
+                value->type(); // Likely to crash if the object was deallocated.
+            ++numValuesInVector;
+        } else {
+            if (type == SortConsistencyCheck)
+                ASSERT(i >= m_storage->m_numValuesInVector);
+        }
+    }
+    ASSERT(numValuesInVector == m_storage->m_numValuesInVector);
+
+    if (m_storage->m_sparseValueMap) {
+        SparseArrayValueMap::iterator end = m_storage->m_sparseValueMap->end();
+        for (SparseArrayValueMap::iterator it = m_storage->m_sparseValueMap->begin(); it != end; ++it) {
+            unsigned index = it->first;
+            ASSERT(index < m_length);
+            ASSERT(index >= m_vectorLength);
+            ASSERT(index <= maxArrayIndex);
+            ASSERT(it->second);
+            if (type != DestructorConsistencyCheck)
+                it->second->type(); // Likely to crash if the object was deallocated.
+        }
+    }
+}
+
+#endif
+
+}