Almost works with current cvs. Initially the first dropdown should have value 
"------ All Makes ----". Also the list of Makes is sorted alphabetically in 
Netscape not in konq.

Edwin.

Hmm. The site uses a for-in construct to iterate over an array's elements,          
and assumes that the order used when filling in the array will be respected.         
    
Since we use an AVL tree to store properties, the ordering isn't kept at all...    
    
The spec for for-in (12.6.4) says "the order of enumeration is defined by the   
object". The Array object has no special treatment for properties that are not  
ints (that's the case here, cf testcase)... I can't find anything related to ordering in 
the definition of Object. Not sure if this is a bug or not, then (it's definitely a 
difference with other browsers, but changing our data structure for storing 
properties.... huh).  
    

Created attachment 238 [details]
testcase

*** Bug 62928 has been marked as a duplicate of this bug. ***

Fixed for KDE 3.3 (latest)

Had to back out of the patch for now. Broke memory managment.

*** Bug 104506 has been marked as a duplicate of this bug. ***

*** Bug 112072 has been marked as a duplicate of this bug. ***

Created attachment 13803 [details]
Patch from WebCore Harri tried to merge

This is patch Harri commited in 2004-02-21 and backed it out because of memory
management problems. I used it during last days without single crash, but it
doesn't mean anything of course - I rarely visit sites which use JavaScript.

Created attachment 13807 [details]
Patch with more merges to PropertyMap from WebCore

I merged some more changes from WebCore to the PropertyMap which might be
related with problems with older patch. And some trivial patches as well on top
of that. This patch is attachement #13803 + merges (revision numbers are from
WebCore CVS repository):

property_map.cpp:1.38, property_map.h:1.20:
- fixed <rdar://problem/3746676> SAP WebDynpro app hangs inside JavaScript
property map hash table code (deleted sentinel problem)

property_map.cpp:1.39:
- initialize deletedElementIndex to make the compiler happy

property_map.cpp:1.41:
[snip big changelog entry]
- Get size and entries pointer outside loop to avoid re-getting them inside the
loop.

property_map.cpp:1.43:
- remove uses of Mac-OS-X-specific MAX macro

I'm using this patch without problems (for now) and put it into production on
my coworkers desktop as well (I'm really tired of their whining about Bug
#112072, that's why I'm doing this merging at all). I'd happy to work on with
this if there will be any problems with this patch.

Any chance that Hasso's patch will get into any 3.5.x release?

I been using this patch for some time while dev. testing stuff from dojotoolkit.org without problems, though I dont know enough about memory manegment to say it works.

With the current hype on Ajax, focus on javascript has risen quite a bit, and anything that would make kjs more "mainstream" would sure help cross browser javascript library development.

In any case, thanks for all the good work in KDE!

Regards
Fredrik Johansson

It can't go in as-is since it breaks binary compatibility. I may try to hack it to be BC for 3.5.3 though.

Thanks Maksim that sure would be nice!

Created attachment 15776 [details]
Binary stable patch, with correct sorting

I spend some evenings to make a patch wich is binary stable and (hopefully)
doesnt crash. I cant make it crash and I have tested it pretty heavily.

Created attachment 15778 [details]
a test case .js file

test adding -> sorting, adding -> removing -> sorting, adding -> removing ->
adding -> sorting.
This testcase assumes that js Array[1,2,3 etc] is sorted correctly, which it
allways should be.

*** Bug 110572 has been marked as a duplicate of this bug. ***

I and one of my coworkers have used the patch from #14 during last week without any problems. Many thanks, Fredrik.

Good to know!

I'm kind of hopeing this patch or a modified version of it can get into 3.5.3
Because it would take away one argument for NOT supporting konqueror, and the less arguments against, the more konqueror supported sites there will be.

Please excuse me bad English
/ Fredrik

SVN commit 556121 by ggarand:

apply patch from  Fredrik Johansson <fredrik@mumme.se>

for correct ordering of array properties

BUG: 28474

approved by Harri



 M  +133 -10   property_map.cpp  


--- branches/KDE/3.5/kdelibs/kjs/property_map.cpp #556120:556121
@@ -63,6 +63,13 @@
     int sizeMask;
     int size;
     int keyCount;
+
+    // gets initialized in expand, an array that stores insert order of a particular hash
+    int *hashToIndex; // NOTE: is one based 1,2,3 etc..
+
+    // keeps trac on how many insertions we have made, cant use keyCount because delete a key in the middle messes things
+    int indexCount;
+
     PropertyMapHashTableEntry entries[1];
 };
 
@@ -102,6 +109,10 @@
         if (key)
 	  key->deref();
     }
+    // fredrik added to cleanup sortorder
+    if (_table)
+        delete [] _table->hashToIndex;
+
     free(_table);
 }
 
@@ -216,7 +227,9 @@
     assert(!name.isNull());
     assert(value != 0);
 
+#if DO_CONSISTENCY_CHECK // speed, why call a stub if we dont need to??
     checkConsistency();
+#endif
 
     UString::Rep *rep = name._ustring.rep;
 
@@ -244,10 +257,8 @@
         }
     }
 #endif
-
     if (!_table || _table->keyCount * 2 >= _table->size)
         expand();
-
     int i = hash(rep);
 #if DUMP_STATISTICS
     ++numProbes;
@@ -270,7 +281,13 @@
     _table->entries[i].attributes = attributes;
     ++_table->keyCount;
 
+    // store insert order
+    _table->indexCount++;
+    _table->hashToIndex[i] = _table->indexCount;
+
+#if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to??
     checkConsistency();
+#endif
 }
 
 inline void PropertyMap::insert(UString::Rep *key, ValueImp *value, int attributes)
@@ -292,42 +309,97 @@
 
 void PropertyMap::expand()
 {
+#if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to??
     checkConsistency();
+#endif
+    Table *oldTable = _table;
 
-    Table *oldTable = _table;
     int oldTableSize = oldTable ? oldTable->size : 0;
 
     int newTableSize = oldTableSize ? oldTableSize * 2 : 16;
-    _table = (Table *)calloc(1, sizeof(Table) + (newTableSize - 1) * sizeof(Entry) );
+
+    // Is this realy the best way? wouldnt it be easier to use new/delete on an array instead
+    // and do a pointer in Table to that array, that way we wouldnt need to delete the whole _table
+    // every time we need to expand
+    _table = (Table *)calloc(1, sizeof(Table) + ((newTableSize - 1) * sizeof(Entry)) );
+
+    int *p = new int[newTableSize];
+    for (int i = 0; i < newTableSize; i++)
+        p[i] = 0;
+
+    _table->hashToIndex = p;
+
     _table->size = newTableSize;
+
     _table->sizeMask = newTableSize - 1;
+
     _table->keyCount = oldTable ? oldTable->keyCount : 0;
 
+    _table->indexCount = oldTable ? oldTable->indexCount : 0;
+
 #if USE_SINGLE_ENTRY
     UString::Rep *key = _singleEntry.key;
     if (key) {
         insert(key, _singleEntry.value, _singleEntry.attributes);
-	_table->keyCount++;
+        _table->keyCount++;
         _singleEntry.key = 0;
+
+        // store sort order
+        // first get the id of newly inserted key, check for trashed hash, then store it
+        int k = hash(key);
+#if DUMP_STATISTICS
+    ++numProbes;
+    numCollisions += _table->entries[k].key && _table->entries[k].key != key;
+#endif
+        while (UString::Rep *newKey = _table->entries[k].key) {
+             if (key == newKey)
+                 break;
+             k = (k + 1) & _table->sizeMask;
+        }
+        _table->indexCount++;
+        _table->hashToIndex[k] = _table->indexCount;
     }
 #endif
 
     for (int i = 0; i != oldTableSize; ++i) {
         UString::Rep *key = oldTable->entries[i].key;
-        if (key)
+        if (key) {
             insert(key, oldTable->entries[i].value, oldTable->entries[i].attributes);
+
+            // store sort order
+            // first get the id of newly inserted key, check for trashed hash, then store it
+            int k = hash(key);
+#if DUMP_STATISTICS
+    ++numProbes;
+    numCollisions += _table->entries[k].key && _table->entries[k].key != key;
+#endif
+            while (UString::Rep *newKey = _table->entries[k].key) {
+                if (key == newKey)
+                    break;
+                k = (k + 1) & _table->sizeMask;
+            }
+            // store hashindex on the newly inserted entry
+            _table->hashToIndex[k] = oldTable->hashToIndex[i];
+        }
     }
 
+    if (oldTable){
+        delete [] oldTable->hashToIndex;
+    }
     free(oldTable);
 
+#if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to??
     checkConsistency();
+#endif
 }
 
 void PropertyMap::remove(const Identifier &name)
 {
     assert(!name.isNull());
 
+#if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to??
     checkConsistency();
+#endif
 
     UString::Rep *rep = name._ustring.rep;
 
@@ -356,6 +428,7 @@
             break;
         i = (i + 1) & _table->sizeMask;
     }
+
     if (!key)
         return;
 
@@ -371,11 +444,30 @@
         key = _table->entries[i].key;
         if (!key)
             break;
+
         _table->entries[i].key = 0;
+
         insert(key, _table->entries[i].value, _table->entries[i].attributes);
+
+        // store the index of the new hash
+        int k = hash(key);
+#if DUMP_STATISTICS
+    ++numProbes;
+    numCollisions += _table->entries[k].key && _table->entries[k].key != key;
+#endif
+        while (UString::Rep *newKey = _table->entries[k].key) {
+            if (key == newKey)
+                break;
+            k = (k + 1) & _table->sizeMask;
+        }
+
+        // store hashindex on the newly moved entry
+        _table->hashToIndex[k] = _table->hashToIndex[i];
     }
 
+#if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to??
     checkConsistency();
+#endif
 }
 
 void PropertyMap::mark() const
@@ -411,15 +503,45 @@
         return;
     }
 
-    for (int i = 0; i != _table->size; ++i) {
-        UString::Rep *key = _table->entries[i].key;
-        if (key && !(_table->entries[i].attributes & DontEnum))
-            list.append(Reference(base, Identifier(key)));
+    // Allocate a buffer to use to sort the keys.
+    int indexSize = _table->indexCount + 1; // indexes is one based
+    UString::Rep **allKeys = new UString::Rep*[indexSize];
+
+    for (int i = 0; i < indexSize; i++)
+        allKeys[i] = NULL;
+
+    // push  valid hashes to the array allKeys, using insert order as index.
+    // we need to pass array hashes instead of pointers to keys, because we got
+    // memory corruption sometimes, seems that Identifier in below call deletes the key
+    int size = _table->size;
+    Entry *entries = _table->entries;
+    for (int i = 0; i != size; ++i) {
+        if (entries[i].key && !(entries[i].attributes & DontEnum)) {
+            int idx = _table->hashToIndex[i];
+            if (idx) {
+                allKeys[idx] = entries[i].key;
+            } else { // nonsorted key, failure
+                //cout<<"Error with in KJS property_map.addEnumerablesToReferenceList \nUnsorted key"<<endl;
+                assert(0==1); // allways throw error if get here
+            }
+        }
     }
+    // Put the keys of the sorted entries into the reference list.
+    for (int i = 0; i < indexSize; ++i) {
+        if (allKeys[i] != NULL){
+            list.append(Reference(base, Identifier(allKeys[i])));
+        }
+        allKeys[i] = NULL; // dont deallocate key by accident, when we delete allKeys
+    }
+
+    // Deallocate the buffer.
+    delete [] allKeys;
 }
 
 void PropertyMap::addSparseArrayPropertiesToReferenceList(ReferenceList &list, const Object &base) const
 {
+    // NOTE: I did'nt add sort in this method because It seems to be referenced in ArrayInstanceImp
+    // only and arrays are sorted by definition, dont need the extra overhead
     if (!_table) {
 #if USE_SINGLE_ENTRY
         UString::Rep *key = _singleEntry.key;
@@ -520,6 +642,7 @@
             i = (i + 1) & _table->sizeMask;
         }
         assert(i == j);
+        assert(_table->hashToIndex[i] > 0);
         count++;
     }
     assert(count == _table->keyCount);