Fix another bug in sweeping the identifier hash table

When an identifier overflows into the next bucket and its original spot
becomes free, it is not only important to move that identifier into the
now free spot. It is also necessary to shift the entries in the bucket
overflowed into one entry to the left, to avoid an accidental terminator
in the bucket. Such a terminator can make entire strings disappear from
the hash table. That in turn may result in repeated insertion of strings
that are otherwise identical, leading to internalClass lookups failing
(despite the members existing) after a GC.

Task-number: QTBUG-70205
Change-Id: Idf931287896a8ff730af98d36de703157e9792d3
Reviewed-by: Liang Qi <liang.qi@qt.io>
Reviewed-by: Lars Knoll <lars.knoll@qt.io>

1 files changed, 58 insertions, 0 deletions

diff --git a/tests/auto/qml/qv4identifiertable/tst_qv4identifiertable.cpp b/tests/auto/qml/qv4identifiertable/tst_qv4identifiertable.cpp
index b2908ac5bb..095943cdc7 100644
--- a/tests/auto/qml/qv4identifiertable/tst_qv4identifiertable.cpp
+++ b/tests/auto/qml/qv4identifiertable/tst_qv4identifiertable.cpp
@@ -41,6 +41,7 @@ private slots:
     void sweepFirstEntryInSameBucketWithDifferingHash();
     void dontSweepAcrossBucketBoundaries();
     void sweepAcrossBucketBoundariesIfFirstBucketFull();
+    void sweepBucketGap();
 };
 
 void tst_qv4identifiertable::sweepFirstEntryInBucket()
@@ -300,6 +301,63 @@ void tst_qv4identifiertable::sweepAcrossBucketBoundariesIfFirstBucketFull()
     QCOMPARE(table.entriesByHash[3], nullptr);
 }
 
+void tst_qv4identifiertable::sweepBucketGap()
+{
+    QV4::ExecutionEngine engine;
+    QV4::IdentifierTable table(&engine, /*numBits*/3);
+
+    auto entry1 = engine.newString(QStringLiteral("one"));
+    auto entry2 = engine.newString(QStringLiteral("two"));
+    auto entry3 = engine.newString(QStringLiteral("three"));
+    auto entry4 = engine.newString(QStringLiteral("four"));
+
+    entry1->createHashValue();
+    entry2->createHashValue();
+    entry3->createHashValue();
+    entry4->createHashValue();
+
+    // We have two buckets where the second entry in the first bucket
+    // flows into the second bucket. So insertion into the second bucket
+    // will shift by one and create
+    // [entry1][entry2 (would map to first but overflows into second), entry3, entry4]
+    // Garbage collecting the first entry should not only move the second entry
+    // into its own first bucket (where there is space now), it is also critical to
+    // not leave a gap but move the third and fourth entries to the beginning of
+    // their bucket:
+    // [entry2][entry3, entry4]
+    entry1->stringHash = 0;  // % 11 -> 0
+    entry2->stringHash = 11; // % 11 -> 0, but ends up at idx 1 because 0 taken
+    entry3->stringHash = 12; // % 11 -> 1, but ends up at idx 2 because 1 taken
+    entry4->stringHash = 12; // % 11 -> 1, but ends up at idx 3 because 1+2 taken
+
+    // trigger insertion
+    table.asPropertyKey(entry1);
+    table.asPropertyKey(entry2);
+    table.asPropertyKey(entry3);
+    table.asPropertyKey(entry4);
+
+    QCOMPARE(table.size, 4);
+    QCOMPARE(table.alloc, 11);
+
+    QCOMPARE(table.entriesByHash[0], entry1);
+    QCOMPARE(table.entriesByHash[1], entry2);
+    QCOMPARE(table.entriesByHash[2], entry3);
+    QCOMPARE(table.entriesByHash[3], entry4);
+    QCOMPARE(table.entriesByHash[4], nullptr);
+
+    // first entry not marked
+    entry2->setMarkBit();
+    entry3->setMarkBit();
+    entry4->setMarkBit();
+
+    table.sweep();
+
+    QCOMPARE(table.entriesByHash[0], entry2);
+    QCOMPARE(table.entriesByHash[1], entry3);
+    QCOMPARE(table.entriesByHash[2], entry4);
+    QCOMPARE(table.entriesByHash[3], nullptr);
+}
+
 QTEST_MAIN(tst_qv4identifiertable)
 
 #include "tst_qv4identifiertable.moc"