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.

Fixes: QTBUG-91687
Task-number: QTBUG-58559
Change-Id: I3238931b5919ed2b98059e0b7f928334284ce7bf
Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
(cherry picked from commit 0b9fa18dfefc06f542bd0c98b7e41fa14aa0c2cf)
Reviewed-by: Qt Cherry-pick Bot <cherrypick_bot@qt-project.org>

11 files changed, 339 insertions, 77 deletions

diff --git a/src/qml/jsruntime/qv4engine.cpp b/src/qml/jsruntime/qv4engine.cpp
index 04205054cd..17cea99fd8 100644
--- a/src/qml/jsruntime/qv4engine.cpp
+++ b/src/qml/jsruntime/qv4engine.cpp
@@ -2186,7 +2186,7 @@ void ExecutionEngine::setQmlEngine(QQmlEngine *engine)
 
 static void freeze_recursive(QV4::ExecutionEngine *v4, QV4::Object *object)
 {
-    if (object->as<QV4::QObjectWrapper>() || object->internalClass()->isFrozen)
+    if (object->as<QV4::QObjectWrapper>() || object->internalClass()->isFrozen())
         return;
 
     QV4::Scope scope(v4);
diff --git a/src/qml/jsruntime/qv4global_p.h b/src/qml/jsruntime/qv4global_p.h
index 3e803def73..9e0eabf3d2 100644
--- a/src/qml/jsruntime/qv4global_p.h
+++ b/src/qml/jsruntime/qv4global_p.h
@@ -271,7 +271,6 @@ struct PropertyAttributes
     void clear() { m_all = 0; }
     bool isEmpty() const { return !m_all; }
 
-    uint flags() const { return m_flags; }
     uint all() const { return m_all; }
 
     bool operator==(PropertyAttributes other) {
diff --git a/src/qml/jsruntime/qv4internalclass.cpp b/src/qml/jsruntime/qv4internalclass.cpp
index 134aaa8433..cfce1425f8 100644
--- a/src/qml/jsruntime/qv4internalclass.cpp
+++ b/src/qml/jsruntime/qv4internalclass.cpp
@@ -142,7 +142,7 @@ void SharedInternalClassDataPrivate<PropertyKey>::setSize(uint s)
     data->values.size = s;
 }
 
-PropertyKey SharedInternalClassDataPrivate<PropertyKey>::at(uint i)
+PropertyKey SharedInternalClassDataPrivate<PropertyKey>::at(uint i) const
 {
     Q_ASSERT(data && i < size());
     return PropertyKey::fromId(data->values.values[i].rawValue());
@@ -229,6 +229,13 @@ namespace Heap {
 
 void InternalClass::init(ExecutionEngine *engine)
 {
+//    InternalClass is automatically zeroed during allocation:
+//    prototype = nullptr;
+//    parent = nullptr;
+//    size = 0;
+//    numRedundantTransitions = 0;
+//    flags = 0;
+
     Base::init();
     new (&propertyTable) PropertyHash();
     new (&nameMap) SharedInternalClassData<PropertyKey>(engine);
@@ -237,13 +244,6 @@ void InternalClass::init(ExecutionEngine *engine)
 
     this->engine = engine;
     vtable = QV4::InternalClass::staticVTable();
-//    prototype = nullptr;
-//    parent = nullptr;
-//    size = 0;
-    extensible = true;
-    isFrozen = false;
-    isSealed = false;
-    isUsedAsProto = false;
     protoId = engine->newProtoId();
 
     // Also internal classes need an internal class pointer. Simply make it point to itself
@@ -264,10 +264,8 @@ void InternalClass::init(Heap::InternalClass *other)
     prototype = other->prototype;
     parent = other;
     size = other->size;
-    extensible = other->extensible;
-    isSealed = other->isSealed;
-    isFrozen = other->isFrozen;
-    isUsedAsProto = other->isUsedAsProto;
+    numRedundantTransitions = other->numRedundantTransitions;
+    flags = other->flags;
     protoId = engine->newProtoId();
 
     internalClass.set(engine, other->internalClass);
@@ -329,7 +327,99 @@ static void addDummyEntry(InternalClass *newClass, PropertyHash::Entry e)
     ++newClass->size;
 }
 
-Heap::InternalClass *InternalClass::changeMember(PropertyKey identifier, PropertyAttributes data, InternalClassEntry *entry)
+static PropertyAttributes attributesFromFlags(int flags)
+{
+    PropertyAttributes attributes;
+    attributes.m_all = uchar(flags);
+    return attributes;
+}
+
+static Heap::InternalClass *cleanInternalClass(Heap::InternalClass *orig)
+{
+    if (++orig->numRedundantTransitions < Heap::InternalClass::MaxRedundantTransitions)
+        return orig;
+
+    // We will generally add quite a few transitions here. We have 255 redundant ones.
+    // We can expect at least as many significant ones in addition.
+    std::vector<InternalClassTransition> transitions;
+
+    Scope scope(orig->engine);
+    Scoped<QV4::InternalClass> child(scope, orig);
+
+    {
+        quint8 remainingRedundantTransitions = orig->numRedundantTransitions;
+        QSet<PropertyKey> properties;
+        int structureChanges = 0;
+
+        Scoped<QV4::InternalClass> parent(scope, orig->parent);
+        while (parent && remainingRedundantTransitions > 0) {
+            Q_ASSERT(child->d() != scope.engine->classes[ExecutionEngine::Class_Empty]);
+            const auto it = std::find_if(
+                        parent->d()->transitions.begin(), parent->d()->transitions.end(),
+                        [&child](const InternalClassTransition &t) {
+                return child->d() == t.lookup;
+            });
+            Q_ASSERT(it != parent->d()->transitions.end());
+
+            if (it->flags & InternalClassTransition::StructureChange) {
+                // A structural change. Each kind of structural change has to be recorded only once.
+                if ((structureChanges & it->flags) != it->flags) {
+                    transitions.push_back(*it);
+                    structureChanges |= it->flags;
+                } else {
+                    --remainingRedundantTransitions;
+                }
+            } else if (!properties.contains(it->id)) {
+                // We only need the final state of the property.
+                properties.insert(it->id);
+
+                // Property removal creates _two_ redundant transitions.
+                // We don't have to replay either, but numRedundantTransitions only records one.
+                if (it->flags != 0)
+                    transitions.push_back(*it);
+            } else {
+                --remainingRedundantTransitions;
+            }
+
+            child = parent->d();
+            parent = child->d()->parent;
+            Q_ASSERT(child->d() != parent->d());
+        }
+    }
+
+    for (auto it = transitions.rbegin(); it != transitions.rend(); ++it) {
+        switch (it->flags) {
+        case InternalClassTransition::NotExtensible:
+            child = child->d()->nonExtensible();
+            continue;
+        case InternalClassTransition::VTableChange:
+            child = child->d()->changeVTable(it->vtable);
+            continue;
+        case InternalClassTransition::PrototypeChange:
+            child = child->d()->changePrototype(it->prototype);
+            continue;
+        case InternalClassTransition::ProtoClass:
+            child = child->d()->asProtoClass();
+            continue;
+        case InternalClassTransition::Sealed:
+            child = child->d()->sealed();
+            continue;
+        case InternalClassTransition::Frozen:
+            child = child->d()->frozen();
+            continue;
+        default:
+            Q_ASSERT(it->flags != 0);
+            Q_ASSERT(it->flags < InternalClassTransition::StructureChange);
+            child = child->addMember(it->id, attributesFromFlags(it->flags));
+            continue;
+        }
+    }
+
+    return child->d();
+}
+
+Heap::InternalClass *InternalClass::changeMember(
+        PropertyKey identifier, PropertyAttributes data, InternalClassEntry *entry)
 {
     if (!data.isEmpty())
         data.resolve();
@@ -345,7 +435,7 @@ Heap::InternalClass *InternalClass::changeMember(PropertyKey identifier, Propert
     }
 
     if (data == propertyData.at(idx))
-        return static_cast<Heap::InternalClass *>(this);
+        return this;
 
     Transition temp = { { identifier }, nullptr, int(data.all()) };
     Transition &t = lookupOrInsertTransition(temp);
@@ -358,7 +448,8 @@ Heap::InternalClass *InternalClass::changeMember(PropertyKey identifier, Propert
         Q_ASSERT(!propertyData.at(idx).isAccessor());
 
         // add a dummy entry for the accessor
-        entry->setterIndex = newClass->size;
+        if (entry)
+            entry->setterIndex = newClass->size;
         e->setterIndex = newClass->size;
         addDummyEntry(newClass, *e);
     }
@@ -367,7 +458,8 @@ Heap::InternalClass *InternalClass::changeMember(PropertyKey identifier, Propert
 
     t.lookup = newClass;
     Q_ASSERT(t.lookup);
-    return newClass;
+
+    return cleanInternalClass(newClass);
 }
 
 Heap::InternalClass *InternalClass::changePrototypeImpl(Heap::Object *proto)
@@ -377,7 +469,7 @@ Heap::InternalClass *InternalClass::changePrototypeImpl(Heap::Object *proto)
     if (proto)
         proto->setUsedAsProto();
     Q_ASSERT(prototype != proto);
-    Q_ASSERT(!proto || proto->internalClass->isUsedAsProto);
+    Q_ASSERT(!proto || proto->internalClass->isUsedAsProto());
 
     Transition temp = { { PropertyKey::invalid() }, nullptr, Transition::PrototypeChange };
     temp.prototype = proto;
@@ -391,8 +483,7 @@ Heap::InternalClass *InternalClass::changePrototypeImpl(Heap::Object *proto)
     newClass->prototype = proto;
 
     t.lookup = newClass;
-
-    return newClass;
+    return prototype ? cleanInternalClass(newClass) : newClass;
 }
 
 Heap::InternalClass *InternalClass::changeVTableImpl(const VTable *vt)
@@ -413,12 +504,14 @@ Heap::InternalClass *InternalClass::changeVTableImpl(const VTable *vt)
     t.lookup = newClass;
     Q_ASSERT(t.lookup);
     Q_ASSERT(newClass->vtable);
-    return newClass;
+    return vtable == QV4::InternalClass::staticVTable()
+            ? newClass
+            : cleanInternalClass(newClass);
 }
 
 Heap::InternalClass *InternalClass::nonExtensible()
 {
-    if (!extensible)
+    if (!isExtensible())
         return this;
 
     Transition temp = { { PropertyKey::invalid() }, nullptr, Transition::NotExtensible};
@@ -427,7 +520,7 @@ Heap::InternalClass *InternalClass::nonExtensible()
         return t.lookup;
 
     Heap::InternalClass *newClass = engine->newClass(this);
-    newClass->extensible = false;
+    newClass->flags |= NotExtensible;
 
     t.lookup = newClass;
     Q_ASSERT(t.lookup);
@@ -464,7 +557,7 @@ Heap::InternalClass *InternalClass::addMember(PropertyKey identifier, PropertyAt
 
 Heap::InternalClass *InternalClass::addMemberImpl(PropertyKey identifier, PropertyAttributes data, InternalClassEntry *entry)
 {
-    Transition temp = { { identifier }, nullptr, (int)data.flags() };
+    Transition temp = { { identifier }, nullptr, int(data.all()) };
     Transition &t = lookupOrInsertTransition(temp);
 
     if (entry) {
@@ -517,21 +610,23 @@ void InternalClass::removeMember(QV4::Object *object, PropertyKey identifier)
     changeMember(object, identifier, Attr_Invalid);
 
 #ifndef QT_NO_DEBUG
-    // we didn't remove the data slot, just made it inaccessible
-    Q_ASSERT(object->internalClass()->size == oldClass->size);
+    // We didn't remove the data slot, just made it inaccessible.
+    // ... unless we've rebuilt the whole class. Then all the deleted properties are gone.
+    Q_ASSERT(object->internalClass()->numRedundantTransitions == 0
+             || object->internalClass()->size == oldClass->size);
 #endif
 }
 
 Heap::InternalClass *InternalClass::sealed()
 {
-    if (isSealed)
+    if (isSealed())
         return this;
 
     Transition temp = { { PropertyKey::invalid() }, nullptr, InternalClassTransition::Sealed };
     Transition &t = lookupOrInsertTransition(temp);
 
     if (t.lookup) {
-        Q_ASSERT(t.lookup && t.lookup->isSealed);
+        Q_ASSERT(t.lookup && t.lookup->isSealed());
         return t.lookup;
     }
 
@@ -539,7 +634,7 @@ Heap::InternalClass *InternalClass::sealed()
     Scoped<QV4::InternalClass> ic(scope, engine->newClass(this));
     Heap::InternalClass *s = ic->d();
 
-    if (!isFrozen) { // freezing also makes all properties non-configurable
+    if (!isFrozen()) { // freezing also makes all properties non-configurable
         for (uint i = 0; i < size; ++i) {
             PropertyAttributes attrs = propertyData.at(i);
             if (attrs.isEmpty())
@@ -548,7 +643,7 @@ Heap::InternalClass *InternalClass::sealed()
             s->propertyData.set(i, attrs);
         }
     }
-    s->isSealed = true;
+    s->flags |= Sealed;
 
     t.lookup = s;
     return s;
@@ -556,14 +651,14 @@ Heap::InternalClass *InternalClass::sealed()
 
 Heap::InternalClass *InternalClass::frozen()
 {
-    if (isFrozen)
+    if (isFrozen())
         return this;
 
     Transition temp = { { PropertyKey::invalid() }, nullptr, InternalClassTransition::Frozen };
     Transition &t = lookupOrInsertTransition(temp);
 
     if (t.lookup) {
-        Q_ASSERT(t.lookup && t.lookup->isFrozen);
+        Q_ASSERT(t.lookup && t.lookup->isFrozen());
         return t.lookup;
     }
 
@@ -580,7 +675,7 @@ Heap::InternalClass *InternalClass::frozen()
         attrs.setConfigurable(false);
         f->propertyData.set(i, attrs);
     }
-    f->isFrozen = true;
+    f->flags |= Frozen;
 
     t.lookup = f;
     return f;
@@ -604,7 +699,7 @@ InternalClass *InternalClass::cryopreserved()
 
 bool InternalClass::isImplicitlyFrozen() const
 {
-    if (isFrozen)
+    if (isFrozen())
         return true;
 
     for (uint i = 0; i < size; ++i) {
@@ -620,7 +715,7 @@ bool InternalClass::isImplicitlyFrozen() const
 
 Heap::InternalClass *InternalClass::asProtoClass()
 {
-    if (isUsedAsProto)
+    if (isUsedAsProto())
         return this;
 
     Transition temp = { { PropertyKey::invalid() }, nullptr, Transition::ProtoClass };
@@ -629,7 +724,7 @@ Heap::InternalClass *InternalClass::asProtoClass()
         return t.lookup;
 
     Heap::InternalClass *newClass = engine->newClass(this);
-    newClass->isUsedAsProto = true;
+    newClass->flags |= UsedAsProto;
 
     t.lookup = newClass;
     Q_ASSERT(t.lookup);
@@ -649,7 +744,7 @@ static void updateProtoUsage(Heap::Object *o, Heap::InternalClass *ic)
 
 void InternalClass::updateProtoUsage(Heap::Object *o)
 {
-    Q_ASSERT(isUsedAsProto);
+    Q_ASSERT(isUsedAsProto());
     Heap::InternalClass *ic = engine->internalClasses(EngineBase::Class_Empty);
     Q_ASSERT(!ic->prototype);
 
@@ -662,6 +757,9 @@ void InternalClass::markObjects(Heap::Base *b, MarkStack *stack)
     if (ic->prototype)
         ic->prototype->mark(stack);
 
+    if (ic->parent)
+        ic->parent->mark(stack);
+
     ic->nameMap.mark(stack);
 }
 
diff --git a/src/qml/jsruntime/qv4internalclass_p.h b/src/qml/jsruntime/qv4internalclass_p.h
index 04cdcd8e4d..6847ccb740 100644
--- a/src/qml/jsruntime/qv4internalclass_p.h
+++ b/src/qml/jsruntime/qv4internalclass_p.h
@@ -137,7 +137,7 @@ struct SharedInternalClassDataPrivate<PropertyAttributes> {
     uint size() const { return m_size; }
     void setSize(uint s) { m_size = s; }
 
-    PropertyAttributes at(uint i) { Q_ASSERT(data && i < m_alloc); return data[i]; }
+    PropertyAttributes at(uint i) const { Q_ASSERT(data && i < m_alloc); return data[i]; }
     void set(uint i, PropertyAttributes t) { Q_ASSERT(data && i < m_alloc); data[i] = t; }
 
     void mark(MarkStack *) {}
@@ -162,7 +162,7 @@ struct SharedInternalClassDataPrivate<PropertyKey> {
     uint size() const;
     void setSize(uint s);
 
-    PropertyKey at(uint i);
+    PropertyKey at(uint i) const;
     void set(uint i, PropertyKey t);
 
     void mark(MarkStack *s);
@@ -253,24 +253,33 @@ struct InternalClassTransition
     int flags;
     enum {
         // range 0-0xff is reserved for attribute changes
-        NotExtensible = 0x100,
-        VTableChange = 0x200,
-        PrototypeChange = 0x201,
-        ProtoClass = 0x202,
-        Sealed = 0x203,
-        Frozen = 0x204
+        StructureChange = 0x100,
+        NotExtensible   = StructureChange | (1 << 0),
+        VTableChange    = StructureChange | (1 << 1),
+        PrototypeChange = StructureChange | (1 << 2),
+        ProtoClass      = StructureChange | (1 << 3),
+        Sealed          = StructureChange | (1 << 4),
+        Frozen          = StructureChange | (1 << 5),
     };
 
     bool operator==(const InternalClassTransition &other) const
     { return id == other.id && flags == other.flags; }
 
     bool operator<(const InternalClassTransition &other) const
-    { return id < other.id || (id == other.id && flags < other.flags); }
+    { return flags < other.flags || (flags == other.flags && id < other.id); }
 };
 
 namespace Heap {
 
 struct InternalClass : Base {
+    enum Flag {
+        NotExtensible = 1 << 0,
+        Sealed        = 1 << 1,
+        Frozen        = 1 << 2,
+        UsedAsProto   = 1 << 3,
+    };
+    enum { MaxRedundantTransitions = 255 };
+
     ExecutionEngine *engine;
     const VTable *vtable;
     quintptr protoId; // unique across the engine, gets changed whenever the proto chain changes
@@ -286,10 +295,13 @@ struct InternalClass : Base {
     InternalClassTransition &lookupOrInsertTransition(const InternalClassTransition &t);
 
     uint size;
-    bool extensible;
-    bool isSealed;
-    bool isFrozen;
-    bool isUsedAsProto;
+    quint8 numRedundantTransitions;
+    quint8 flags;
+
+    bool isExtensible() const { return !(flags & NotExtensible); }
+    bool isSealed() const { return flags & Sealed; }
+    bool isFrozen() const { return flags & Frozen; }
+    bool isUsedAsProto() const { return flags & UsedAsProto; }
 
     void init(ExecutionEngine *engine);
     void init(InternalClass *other);
diff --git a/src/qml/jsruntime/qv4object.cpp b/src/qml/jsruntime/qv4object.cpp
index 4325af836d..aec04b167d 100644
--- a/src/qml/jsruntime/qv4object.cpp
+++ b/src/qml/jsruntime/qv4object.cpp
@@ -25,17 +25,52 @@ DEFINE_OBJECT_VTABLE(Object);
 
 void Object::setInternalClass(Heap::InternalClass *ic)
 {
-    d()->internalClass.set(engine(), ic);
-    if (ic->isUsedAsProto)
-        ic->updateProtoUsage(d());
     Q_ASSERT(ic && ic->vtable);
-    uint nInline = d()->vtable()->nInlineProperties;
-    if (ic->size <= nInline)
-        return;
-    bool hasMD = d()->memberData != nullptr;
-    uint requiredSize = ic->size - nInline;
-    if (!(hasMD && requiredSize) || (hasMD && d()->memberData->values.size < requiredSize))
-        d()->memberData.set(ic->engine, MemberData::allocate(ic->engine, requiredSize, d()->memberData));
+    Heap::Object *p = d();
+
+    if (ic->numRedundantTransitions < p->internalClass.get()->numRedundantTransitions) {
+        // IC was rebuilt. The indices are different now. We need to move everything.
+
+        Scope scope(engine());
+
+        // We allocate before setting the new IC. Protect it from GC.
+        Scoped<InternalClass> newIC(scope, ic);
+
+        // Pick the members of the old IC that are still valid in the new IC.
+        // Order them by index in memberData (or inline data).
+        Scoped<MemberData> newMembers(scope, MemberData::allocate(scope.engine, ic->size));
+        for (uint i = 0; i < ic->size; ++i)
+            newMembers->set(scope.engine, i, get(ic->nameMap.at(i)));
+
+        p->internalClass.set(scope.engine, ic);
+        const uint nInline = p->vtable()->nInlineProperties;
+
+        if (ic->size > nInline)
+            p->memberData.set(scope.engine, MemberData::allocate(ic->engine, ic->size - nInline));
+        else
+            p->memberData.set(scope.engine, nullptr);
+
+        const auto &memberValues = newMembers->d()->values;
+        for (uint i = 0; i < ic->size; ++i)
+            setProperty(i, memberValues[i]);
+    } else {
+        // The old indices are still the same. No need to move any values.
+        // We may need to re-allocate, though.
+
+        p->internalClass.set(ic->engine, ic);
+        const uint nInline = p->vtable()->nInlineProperties;
+        if (ic->size > nInline) {
+            const uint requiredSize = ic->size - nInline;
+            if ((p->memberData ? p->memberData->values.size : 0) < requiredSize) {
+                p->memberData.set(ic->engine, MemberData::allocate(
+                                      ic->engine, requiredSize, p->memberData));
+            }
+        }
+    }
+
+    if (ic->isUsedAsProto())
+        ic->updateProtoUsage(p);
+
 }
 
 void Object::getProperty(const InternalClassEntry &entry, Property *p) const
@@ -922,7 +957,7 @@ bool Object::virtualDefineOwnProperty(Managed *m, PropertyKey id, const Property
 
 bool Object::virtualIsExtensible(const Managed *m)
 {
-    return m->d()->internalClass->extensible;
+    return m->d()->internalClass->isExtensible();
 }
 
 bool Object::virtualPreventExtensions(Managed *m)
@@ -946,7 +981,7 @@ bool Object::virtualSetPrototypeOf(Managed *m, const Object *proto)
     Heap::Object *protod = proto ? proto->d() : nullptr;
     if (current == protod)
         return true;
-    if (!o->internalClass()->extensible)
+    if (!o->internalClass()->isExtensible())
         return false;
     Heap::Object *p = protod;
     while (p) {
diff --git a/src/qml/jsruntime/qv4propertykey_p.h b/src/qml/jsruntime/qv4propertykey_p.h
index 87a8ed6392..a0e10e7675 100644
--- a/src/qml/jsruntime/qv4propertykey_p.h
+++ b/src/qml/jsruntime/qv4propertykey_p.h
@@ -15,6 +15,7 @@
 //
 
 #include <private/qv4global_p.h>
+#include <QtCore/qhashfunctions.h>
 
 QT_BEGIN_NAMESPACE
 
@@ -109,6 +110,7 @@ public:
     bool operator ==(const PropertyKey &other) const { return val == other.val; }
     bool operator !=(const PropertyKey &other) const { return val != other.val; }
     bool operator <(const PropertyKey &other) const { return val < other.val; }
+    friend size_t qHash(const PropertyKey &key, size_t seed = 0) { return qHash(key.val, seed); }
 };
 
 }
diff --git a/src/qml/jsruntime/qv4qobjectwrapper.cpp b/src/qml/jsruntime/qv4qobjectwrapper.cpp
index b04a7db174..d5e6c1b84a 100644
--- a/src/qml/jsruntime/qv4qobjectwrapper.cpp
+++ b/src/qml/jsruntime/qv4qobjectwrapper.cpp
@@ -752,7 +752,7 @@ bool QObjectWrapper::virtualPut(Managed *m, PropertyKey id, const Value &value,
     QObjectWrapper *that = static_cast<QObjectWrapper*>(m);
     ScopedString name(scope, id.asStringOrSymbol());
 
-    if (that->internalClass()->isFrozen) {
+    if (that->internalClass()->isFrozen()) {
         QString error = QLatin1String("Cannot assign to property \"") +
                         name->toQString() + QLatin1String("\" of read-only object");
         scope.engine->throwError(error);
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 40e8fbe26b..87995b0aca 100644
--- a/tests/auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp
+++ b/tests/auto/qml/qqmlecmascript/tst_qqmlecmascript.cpp
@@ -407,6 +407,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);
@@ -10069,6 +10071,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()