V4: Mark InternalClass parents when running GC

We need to preserve them as they notify us about protoId related
changes. In order to avoid wasting heap space in case many properties
are added and removed from the same object, we put a mechanism in place
to rebuild the InternalClass hierarchy if many redundant transitions are
detected.

Amends commit 69d76d59cec0dcff4c52eef24e779fbef14beeca.

Pick-to: 5.15 6.2 6.3 6.4
Fixes: QTBUG-91687
Task-number: QTBUG-58559
Change-Id: I3238931b5919ed2b98059e0b7f928334284ce7bf
Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>

4 files changed, 129 insertions, 13 deletions

diff --git a/tests/auto/qml/qqmlecmascript/data/internalClassParentGc.js b/tests/auto/qml/qqmlecmascript/data/internalClassParentGc.js
new file mode 100644
index 0000000000..f51ab662ab
--- /dev/null
+++ b/tests/auto/qml/qqmlecmascript/data/internalClassParentGc.js
@@ -0,0 +1,29 @@
+function init() {
+    Array.prototype.doPush = Array.prototype.push
+}
+
+function nasty() {
+    var sc_Vector = Array;
+    var push = sc_Vector.prototype.doPush;
+
+    // Change the memberData to hold something nasty on the current internalClass
+    sc_Vector.prototype.doPush = 5;
+
+    // Trigger a re-allocation of memberData
+    for (var i = 0; i < 256; ++i)
+        sc_Vector.prototype[i + "string"] = function() { return 98; }
+
+    // Change the (new) memberData back, to hold our doPush function again.
+    // This should propagate a protoId change all the way up to the lookup.
+    sc_Vector.prototype.doPush = push;
+}
+
+function func() {
+    var b = [];
+
+    // This becomes a lookup internally, which stores protoId and a pointer
+    // into the memberData. It should get invalidated when memberData is re-allocated.
+    b.doPush(3);
+
+    return b;
+}
diff --git a/tests/auto/qml/qqmlecmascript/data/internalClassParentGc.qml b/tests/auto/qml/qqmlecmascript/data/internalClassParentGc.qml
new file mode 100644
index 0000000000..e313770bf5
--- /dev/null
+++ b/tests/auto/qml/qqmlecmascript/data/internalClassParentGc.qml
@@ -0,0 +1,13 @@
+import QtQml
+
+import "internalClassParentGc.js" as Foo
+
+QtObject {
+    Component.onCompleted: {
+        gc();
+        Foo.init();
+        Foo.func();
+        Foo.nasty();
+        objectName = Foo.func()[0];
+    }
+}
diff --git a/tests/auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp b/tests/auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp
index 033de56695..dca84acd35 100644
--- a/tests/auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp
+++ b/tests/auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp
@@ -408,6 +408,8 @@ private slots:
     void functionNameInFunctionScope();
     void functionAsDefaultArgument();
 
+    void internalClassParentGc();
+
 private:
 //    static void propertyVarWeakRefCallback(v8::Persistent<v8::Value> object, void* parameter);
     static void verifyContextLifetime(const QQmlRefPointer<QQmlContextData> &ctxt);
@@ -10135,6 +10137,15 @@ void tst_qqmlecmascript::functionAsDefaultArgument()
     QCOMPARE(root->objectName(), "didRun");
 }
 
+void tst_qqmlecmascript::internalClassParentGc()
+{
+    QQmlEngine engine;
+    QQmlComponent component(&engine, testFileUrl("internalClassParentGc.qml"));
+    QScopedPointer root(component.create());
+    QVERIFY(root);
+    QCOMPARE(root->objectName(), "3");
+}
+
 QTEST_MAIN(tst_qqmlecmascript)
 
 #include "tst_qqmlecmascript.moc"
diff --git a/tests/auto/qml/qv4mm/tst_qv4mm.cpp b/tests/auto/qml/qv4mm/tst_qv4mm.cpp
index ab324548e7..e5f8951825 100644
--- a/tests/auto/qml/qv4mm/tst_qv4mm.cpp
+++ b/tests/auto/qml/qv4mm/tst_qv4mm.cpp
@@ -25,7 +25,7 @@ private slots:
     void gcStats();
     void multiWrappedQObjects();
     void accessParentOnDestruction();
-    void clearICParent();
+    void cleanInternalClasses();
     void createObjectsOnDestruction();
 };
 
@@ -94,16 +94,41 @@ void tst_qv4mm::accessParentOnDestruction()
     QCOMPARE(obj->property("destructions").toInt(), 100);
 }
 
-void tst_qv4mm::clearICParent()
+void tst_qv4mm::cleanInternalClasses()
 {
     QV4::ExecutionEngine engine;
     QV4::Scope scope(engine.rootContext());
     QV4::ScopedObject object(scope, engine.newObject());
+    QV4::ScopedObject prototype(scope, engine.newObject());
+
+    // Set a prototype so that we get a unique IC.
+    object->setPrototypeOf(prototype);
+
+    QV4::Scoped<QV4::InternalClass> prevIC(scope, object->internalClass());
+    QVERIFY(prevIC->d()->transitions.empty());
+
+    uint prevIcChainLength = 0;
+    for (QV4::Heap::InternalClass *ic = object->internalClass(); ic; ic = ic->parent)
+        ++prevIcChainLength;
+
+    const auto checkICCHainLength = [&]() {
+        uint icChainLength = 0;
+        for (QV4::Heap::InternalClass *ic = object->internalClass(); ic; ic = ic->parent)
+            ++icChainLength;
+
+        const uint redundant = object->internalClass()->numRedundantTransitions;
+        QVERIFY(redundant <= QV4::Heap::InternalClass::MaxRedundantTransitions);
+
+        // A removal makes two transitions redundant.
+        QVERIFY(icChainLength <= prevIcChainLength + 2 * redundant);
+    };
+
+    const uint numTransitions = 16 * 1024;
 
     // Keep identifiers in a separate array so that we don't have to allocate them in the loop that
     // should test the GC on InternalClass allocations.
     QV4::ScopedArrayObject identifiers(scope, engine.newArrayObject());
-    for (uint i = 0; i < 16 * 1024; ++i) {
+    for (uint i = 0; i < numTransitions; ++i) {
         QV4::Scope scope(&engine);
         QV4::ScopedString s(scope);
         s = engine.newIdentifier(QString::fromLatin1("key%1").arg(i));
@@ -114,22 +139,60 @@ void tst_qv4mm::clearICParent()
         object->insertMember(s, v);
     }
 
-    // When allocating the InternalClass objects required for deleting properties, the GC should
-    // eventually run and remove all but the last two.
-    // If we ever manage to avoid allocating the InternalClasses in the first place we will need
-    // to change this test.
-    for (uint i = 0; i < 16 * 1024; ++i) {
+    // There is a chain of ICs originating from the original class.
+    QCOMPARE(prevIC->d()->transitions.size(), 1u);
+    QVERIFY(prevIC->d()->transitions.front().lookup != nullptr);
+
+    // When allocating the InternalClass objects required for deleting properties, eventually
+    // the IC chain gets truncated, dropping all the removed properties.
+    for (uint i = 0; i < numTransitions; ++i) {
         QV4::Scope scope(&engine);
         QV4::ScopedString s(scope, identifiers->get(i));
         QV4::Scoped<QV4::InternalClass> ic(scope, object->internalClass());
         QVERIFY(ic->d()->parent != nullptr);
-        object->deleteProperty(s->toPropertyKey());
+        QV4::ScopedValue val(scope, object->get(s->toPropertyKey()));
+        QCOMPARE(val->toNumber(), double(i));
+        QVERIFY(object->deleteProperty(s->toPropertyKey()));
+        QVERIFY(!object->hasProperty(s->toPropertyKey()));
         QVERIFY(object->internalClass() != ic->d());
-        QCOMPARE(object->internalClass()->parent, ic->d());
-        if (ic->d()->parent == nullptr)
-            return;
     }
-    QFAIL("Garbage collector was not triggered by large amount of InternalClasses");
+
+    // None of the properties we've added are left
+    for (uint i = 0; i < numTransitions; ++i) {
+        QV4::ScopedString s(scope, identifiers->get(i));
+        QVERIFY(!object->hasProperty(s->toPropertyKey()));
+    }
+
+    // Also no other properties have appeared
+    QScopedPointer<QV4::OwnPropertyKeyIterator> iterator(object->ownPropertyKeys(object));
+    QVERIFY(!iterator->next(object).isValid());
+
+    checkICCHainLength();
+
+    // Add and remove properties until it clears all remaining redundant ones
+    uint i = 0;
+    while (object->internalClass()->numRedundantTransitions > 0) {
+        i = (i + 1) % numTransitions;
+        QV4::ScopedString s(scope, identifiers->get(i));
+        QV4::ScopedValue v(scope);
+        v->setDouble(i);
+        object->insertMember(s, v);
+        QVERIFY(object->deleteProperty(s->toPropertyKey()));
+    }
+
+    // Make sure that all dangling ICs are actually gone.
+    scope.engine->memoryManager->runGC();
+
+    // Now the GC has removed the ICs we originally added by adding properties.
+    QVERIFY(prevIC->d()->transitions.empty() || prevIC->d()->transitions.front().lookup == nullptr);
+
+    // Same thing with redundant prototypes
+    for (uint i = 0; i < numTransitions; ++i) {
+        QV4::ScopedObject prototype(scope, engine.newObject());
+        object->setPrototypeOf(prototype); // Makes previous prototype redundant
+    }
+
+    checkICCHainLength();
 }
 
 void tst_qv4mm::createObjectsOnDestruction()