Changeset 2846 in webkit

Timestamp:

Nov 23, 2002, 11:49:26 PM (23 years ago)

Author:

mjs

Message:

• completed Darin's mostly-fix for 3037795 - Resource use increases when accessing very high index value in array

The two missing pieces were handling sparse properties when
shrinking the array, and when sorting. Thse are now both taken
care of.

• kjs/array_instance.h:
• kjs/array_object.cpp: (ArrayInstanceImp::put): (ArrayInstanceImp::deleteProperty): (ArrayInstanceImp::resizeStorage): (ArrayInstanceImp::setLength): (ArrayInstanceImp::sort): (ArrayInstanceImp::pushUndefinedObjectsToEnd):
• kjs/identifier.h:
• kjs/object.h:
• kjs/property_map.cpp:
• kjs/property_map.h:
• kjs/reference_list.cpp: (ReferenceList::append): (ReferenceList::length):
• kjs/reference_list.h:
• kjs/ustring.cpp: (UString::toUInt32):
• kjs/ustring.h:

Location:

trunk/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• ChangeLog-2002-12-03 (modified) (1 diff)
• ChangeLog-2003-10-25 (modified) (1 diff)
• kjs/array_instance.h (modified) (1 diff)
• kjs/array_object.cpp (modified) (10 diffs)
• kjs/identifier.h (modified) (1 diff)
• kjs/object.h (modified) (1 diff)
• kjs/property_map.cpp (modified) (1 diff)
• kjs/property_map.h (modified) (1 diff)
• kjs/reference_list.cpp (modified) (2 diffs)
• kjs/reference_list.h (modified) (1 diff)
• kjs/ustring.cpp (modified) (1 diff)
• kjs/ustring.h (modified) (2 diffs)

trunk/JavaScriptCore/ChangeLog

@@ +1 @@
+2002-11-23  Maciej Stachowiak  <[email protected]>
+
+        - completed Darin's mostly-fix for 3037795 - Resource use
+        increases when accessing very high index value in array
+
+        The two missing pieces were handling sparse properties when
+        shrinking the array, and when sorting. Thse are now both taken
+        care of.
+        
+        * kjs/array_instance.h:
+        * kjs/array_object.cpp:
+        (ArrayInstanceImp::put):
+        (ArrayInstanceImp::deleteProperty):
+        (ArrayInstanceImp::resizeStorage):
+        (ArrayInstanceImp::setLength):
+        (ArrayInstanceImp::sort):
+        (ArrayInstanceImp::pushUndefinedObjectsToEnd):
+        * kjs/identifier.h:
+        * kjs/object.h:
+        * kjs/property_map.cpp:
+        * kjs/property_map.h:
+        * kjs/reference_list.cpp:
+        (ReferenceList::append):
+        (ReferenceList::length):
+        * kjs/reference_list.h:
+        * kjs/ustring.cpp:
+        (UString::toUInt32):
+        * kjs/ustring.h:
+
 2002-11-23  Maciej Stachowiak  <[email protected]>
 

trunk/JavaScriptCore/ChangeLog-2002-12-03

@@ +1 @@
+2002-11-23  Maciej Stachowiak  <[email protected]>
+
+        - completed Darin's mostly-fix for 3037795 - Resource use
+        increases when accessing very high index value in array
+
+        The two missing pieces were handling sparse properties when
+        shrinking the array, and when sorting. Thse are now both taken
+        care of.
+        
+        * kjs/array_instance.h:
+        * kjs/array_object.cpp:
+        (ArrayInstanceImp::put):
+        (ArrayInstanceImp::deleteProperty):
+        (ArrayInstanceImp::resizeStorage):
+        (ArrayInstanceImp::setLength):
+        (ArrayInstanceImp::sort):
+        (ArrayInstanceImp::pushUndefinedObjectsToEnd):
+        * kjs/identifier.h:
+        * kjs/object.h:
+        * kjs/property_map.cpp:
+        * kjs/property_map.h:
+        * kjs/reference_list.cpp:
+        (ReferenceList::append):
+        (ReferenceList::length):
+        * kjs/reference_list.h:
+        * kjs/ustring.cpp:
+        (UString::toUInt32):
+        * kjs/ustring.h:
+
 2002-11-23  Maciej Stachowiak  <[email protected]>
 

trunk/JavaScriptCore/ChangeLog-2003-10-25

@@ +1 @@
+2002-11-23  Maciej Stachowiak  <[email protected]>
+
+        - completed Darin's mostly-fix for 3037795 - Resource use
+        increases when accessing very high index value in array
+
+        The two missing pieces were handling sparse properties when
+        shrinking the array, and when sorting. Thse are now both taken
+        care of.
+        
+        * kjs/array_instance.h:
+        * kjs/array_object.cpp:
+        (ArrayInstanceImp::put):
+        (ArrayInstanceImp::deleteProperty):
+        (ArrayInstanceImp::resizeStorage):
+        (ArrayInstanceImp::setLength):
+        (ArrayInstanceImp::sort):
+        (ArrayInstanceImp::pushUndefinedObjectsToEnd):
+        * kjs/identifier.h:
+        * kjs/object.h:
+        * kjs/property_map.cpp:
+        * kjs/property_map.h:
+        * kjs/reference_list.cpp:
+        (ReferenceList::append):
+        (ReferenceList::length):
+        * kjs/reference_list.h:
+        * kjs/ustring.cpp:
+        (UString::toUInt32):
+        * kjs/ustring.h:
+
 2002-11-23  Maciej Stachowiak  <[email protected]>
 

trunk/JavaScriptCore/kjs/array_instance.h

@@ -53 +53 @@
     
   private:
-    void setLength(unsigned newLength);
+    void setLength(unsigned newLength, ExecState *exec);
     
-    unsigned pushUndefinedObjectsToEnd();
+    unsigned pushUndefinedObjectsToEnd(ExecState *exec);
     
+    void resizeStorage(unsigned);
+
     unsigned length;
     unsigned storageLength;

trunk/JavaScriptCore/kjs/array_object.cpp

@@ -105 +105 @@
 {
   if (propertyName == lengthPropertyName) {
-    setLength(value.toUInt32(exec));
+    setLength(value.toUInt32(exec), exec);
     return;
   }
@@ -113 +113 @@
   if (ok) {
     if (length <= index)
-      setLength(index + 1);
+      setLength(index + 1, exec);
     if (index < storageLength) {
       storage[index] = value.imp();
@@ -126 +126 @@
 {
   if (length <= index)
-    setLength(index + 1);
+    setLength(index + 1, exec);
   if (index < storageLength) {
     storage[index] = value.imp();
@@ -172 +172 @@
   
   bool ok;
-  unsigned index = propertyName.toULong(&ok);
+  uint32_t index = propertyName.toUInt32(&ok);
   if (ok) {
     if (index >= length)
@@ -197 +197 @@
 }
 
-void ArrayInstanceImp::setLength(unsigned newLength)
-{
-  if (newLength <= sparseArrayCutoff || newLength == length + 1) {
+void ArrayInstanceImp::resizeStorage(unsigned newLength)
+{
     if (newLength < storageLength) {
       memset(storage + newLength, 0, sizeof(ValueImp *) * (storageLength - newLength));
@@ -210 +209 @@
     }
     storageLength = newLength;
-  }
-  
-  // FIXME: Need to remove items from the property map when making a sparse
-  // list shorter.
+}
+
+void ArrayInstanceImp::setLength(unsigned newLength, ExecState *exec)
+{
+  if (newLength <= MAX(sparseArrayCutoff,storageLength) || newLength == length + 1) {
+    resizeStorage(newLength);
+  }
+
+  if (newLength < length) {
+    ReferenceList sparseProperties;
+    
+    _prop.addSparseArrayPropertiesToReferenceList(sparseProperties, Object(this));
+    
+    ReferenceListIterator it = sparseProperties.begin();
+    while (it != sparseProperties.end()) {
+      Reference ref = it++;
+      bool ok;
+      if (ref.getPropertyName(exec).toULong(&ok) > newLength) {
+        ref.deleteValue(exec);
+      }
+    }
+  }
   
   length = newLength;
@@ -239 +256 @@
 void ArrayInstanceImp::sort(ExecState *exec)
 {
-    int lengthNotIncludingUndefined = pushUndefinedObjectsToEnd();
+    int lengthNotIncludingUndefined = pushUndefinedObjectsToEnd(exec);
     
     execForCompareByStringForQSort = exec;
@@ -277 +294 @@
 void ArrayInstanceImp::sort(ExecState *exec, Object &compareFunction)
 {
-    int lengthNotIncludingUndefined = pushUndefinedObjectsToEnd();
+    int lengthNotIncludingUndefined = pushUndefinedObjectsToEnd(exec);
     
     CompareWithCompareFunctionArguments args(exec, compareFunction.imp());
@@ -285 +302 @@
 }
 
-unsigned ArrayInstanceImp::pushUndefinedObjectsToEnd()
+unsigned ArrayInstanceImp::pushUndefinedObjectsToEnd(ExecState *exec)
 {
     ValueImp *undefined = UndefinedImp::staticUndefined;
@@ -300 +317 @@
     }
     
-    // FIXME: Get sparse items down here.
-    
-    if (o != storageLength)
+    ReferenceList sparseProperties;
+    _prop.addSparseArrayPropertiesToReferenceList(sparseProperties, Object(this));
+    unsigned newLength = o + sparseProperties.length();
+
+    if (newLength > storageLength) {
+      resizeStorage(newLength);
+    } 
+
+    ReferenceListIterator it = sparseProperties.begin();
+    while (it != sparseProperties.end()) {
+      Reference ref = it++;
+      storage[o] = ref.getValue(exec).imp();
+      ObjectImp::deleteProperty(exec, ref.getPropertyName(exec));
+      o++;
+    }
+    
+    if (newLength != storageLength)
         memset(storage + o, 0, sizeof(ValueImp *) * (storageLength - o));
     

trunk/JavaScriptCore/kjs/identifier.h

@@ -50 +50 @@
         
         unsigned long toULong(bool *ok) const { return _ustring.toULong(ok); }
+        uint32_t toUInt32(bool *ok) const { return _ustring.toUInt32(ok); }
         double toDouble() const { return _ustring.toDouble(); }
         

trunk/JavaScriptCore/kjs/object.h

@@ -598 +598 @@
     void restoreProperties(const SavedProperties &p) { _prop.restore(p); }
 
+  protected:
+    PropertyMap _prop;
   private:
     const HashEntry* findPropertyHashEntry( const Identifier& propertyName ) const;
-    PropertyMap _prop;
     ValueImp *_proto;
     ValueImp *_internalValue;

trunk/JavaScriptCore/kjs/property_map.cpp

@@ -370 +370 @@
 }
 
+void PropertyMap::addSparseArrayPropertiesToReferenceList(ReferenceList &list, const Object &base) const
+{
+#if USE_SINGLE_ENTRY
+    UString::Rep *key = _singleEntry.key;
+    if (key) {
+      UString k(key);
+      bool fitsInUInt32;
+      k.toUInt32(&fitsInUInt32);
+      if (fitsInUInt32) {
+        list.append(Reference(base, Identifier(key)));
+      }
+    }
+#endif
+    if (!_table) {
+      return;
+    }
+
+    for (int i = 0; i != _table->size; ++i) {
+      UString::Rep *key = _table->entries[i].key;
+      if (key) {
+        UString k(key);
+        bool fitsInUInt32;
+        k.toUInt32(&fitsInUInt32);
+        if (fitsInUInt32) {
+          list.append(Reference(base, Identifier(key)));
+        }
+      }
+    }
+}
+
 void PropertyMap::save(SavedProperties &p) const
 {

trunk/JavaScriptCore/kjs/property_map.h

@@ -72 +72 @@
         void mark() const;
         void addEnumerablesToReferenceList(ReferenceList &, const Object &) const;
+        void addSparseArrayPropertiesToReferenceList(ReferenceList &, const Object &) const;
 
         void save(SavedProperties &) const;

trunk/JavaScriptCore/kjs/reference_list.cpp

@@ -42 +42 @@
     ReferenceListHeadNode(const Reference &ref) : ReferenceListNode(ref), refcount(1) {}
     int refcount;
+    int length;
   };
 
@@ -93 +94 @@
     tail = tail->next;
   }
+  head->length++;
+}
+
+int ReferenceList::length()
+{
+  return head ? head->length : 0;
 }
 

trunk/JavaScriptCore/kjs/reference_list.h

@@ -54 +54 @@
 
     void append(const Reference& val);
-    
+    int length();
+
     ReferenceListIterator begin() const;
     ReferenceListIterator end() const;

trunk/JavaScriptCore/kjs/ustring.cpp

@@ -552 +552 @@
 }
 
+uint32_t UString::toUInt32(bool *ok) const
+{
+  double d = toDouble();
+  bool b = true;
+
+  if (isNaN(d) || d != static_cast<uint32_t>(d)) {
+    b = false;
+    d = 0;
+  }
+
+  if (ok)
+    *ok = b;
+
+  return static_cast<uint32_t>(d);
+}
+
 int UString::find(const UString &f, int pos) const
 {

trunk/JavaScriptCore/kjs/ustring.h

@@ -33 +33 @@
 #endif
 
+#include <stdint.h>
+
 /**
  * @internal
@@ -384 +386 @@
      */
     unsigned long toULong(bool *ok = 0L) const;
+
+    uint32_t toUInt32(bool *ok = 0L) const;
+
     /**
      * @return Position of first occurence of f starting at position pos.