Bug 28474

Summary: Ordering of array properties (www.autotrader.ca)
Product: [Applications] konqueror Reporter: jsward
Component: kjsAssignee: Konqueror Developers <konq-bugs>
Status: RESOLVED FIXED    
Severity: normal CC: bht, hasso, maksim, phoenixreads, rohan.beckles
Priority: NOR    
Version: 2.1.1   
Target Milestone: ---   
Platform: RedHat Enterprise Linux   
OS: Linux   
Latest Commit: Version Fixed In:
Attachments: testcase
Patch from WebCore Harri tried to merge
Patch with more merges to PropertyMap from WebCore
Binary stable patch, with correct sorting
a test case .js file

Description jsward 2001-07-08 17:10:30 UTC
(*** This bug was imported into bugs.kde.org ***)

Package:           kjs
Version:           2.1.1 (using KDE 2.1.1 )
Severity:          normal
Installed from:    RedHat RPMs
Compiler:          Stock Redhat 7.1
OS:                Linux
OS/Compiler notes: Same problem with default KDE install in Suse 7.2

On the web page "http://www.trader.ca/search/default.asp?category=1&categoryid=1"
there are two drop down memus one for selecting the make car you are interested in and the model.  Normally (in MS IE) the Make field is filled with manufacturers and when you select one the Model field fills with appropriate models.  However in Konquerer the drop downs only contain "---------- Select Make -------".  It appears that they should be filled in by Javascript embedded in the in page.


(Submitted via bugs.kde.org)
Comment 1 Edwin Schepers 2001-12-19 18:48:49 UTC
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.
Comment 2 David Faure 2002-10-21 13:36:53 UTC
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).  
    
Comment 3 David Faure 2002-10-21 13:43:52 UTC
Created attachment 238 [details]
testcase
Comment 4 Harri Porten 2003-11-13 18:20:18 UTC
*** Bug 62928 has been marked as a duplicate of this bug. ***
Comment 5 Harri Porten 2004-02-21 13:25:42 UTC
Fixed for KDE 3.3 (latest)
Comment 6 Harri Porten 2004-02-21 17:15:54 UTC
Had to back out of the patch for now. Broke memory managment.
Comment 7 Thiago Macieira 2005-04-26 04:39:36 UTC
*** Bug 104506 has been marked as a duplicate of this bug. ***
Comment 8 Maksim Orlovich 2005-09-05 16:16:22 UTC
*** Bug 112072 has been marked as a duplicate of this bug. ***
Comment 9 Hasso Tepper 2005-12-07 14:23:53 UTC
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.
Comment 10 Hasso Tepper 2005-12-07 14:52:59 UTC
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.
Comment 11 Fredrik Johansson 2006-03-15 10:45:10 UTC
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
Comment 12 Maksim Orlovich 2006-03-15 16:01:44 UTC
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.
Comment 13 Fredrik Johansson 2006-03-16 07:42:22 UTC
Thanks Maksim that sure would be nice!
Comment 14 Fredrik Johansson 2006-04-25 23:37:09 UTC
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.
Comment 15 Fredrik Johansson 2006-04-25 23:42:33 UTC
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.
Comment 16 Maksim Orlovich 2006-04-28 19:31:05 UTC
*** Bug 110572 has been marked as a duplicate of this bug. ***
Comment 17 Hasso Tepper 2006-05-04 08:46:21 UTC
I and one of my coworkers have used the patch from #14 during last week without any problems. Many thanks, Fredrik.
Comment 18 Fredrik Johansson 2006-05-06 23:46:27 UTC
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
Comment 19 Germain Garand 2006-06-29 12:05:14 UTC
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);