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)

6 files changed, 212 insertions, 63 deletions

diff --git a/src/qml/jsruntime/qv4engine.cpp b/src/qml/jsruntime/qv4engine.cpp
index f66de35428..828d755e0e 100644
--- a/src/qml/jsruntime/qv4engine.cpp
+++ b/src/qml/jsruntime/qv4engine.cpp
@@ -2030,7 +2030,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 7a7720020b..56369c1103 100644
--- a/src/qml/jsruntime/qv4global_p.h
+++ b/src/qml/jsruntime/qv4global_p.h
@@ -303,7 +303,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 fd98a293d6..c0d6657fce 100644
--- a/src/qml/jsruntime/qv4internalclass.cpp
+++ b/src/qml/jsruntime/qv4internalclass.cpp
@@ -178,7 +178,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());
@@ -265,6 +265,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);
@@ -273,13 +280,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
@@ -300,10 +300,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);
@@ -365,7 +363,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();
@@ -381,7 +471,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);
@@ -394,7 +484,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);
     }
@@ -403,7 +494,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)
@@ -413,7 +505,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;
@@ -427,8 +519,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)
@@ -449,12 +540,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};
@@ -463,7 +556,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);
@@ -500,7 +593,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) {
@@ -553,21 +646,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;
     }
 
@@ -575,7 +670,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())
@@ -584,7 +679,7 @@ Heap::InternalClass *InternalClass::sealed()
             s->propertyData.set(i, attrs);
         }
     }
-    s->isSealed = true;
+    s->flags |= Sealed;
 
     t.lookup = s;
     return s;
@@ -592,14 +687,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;
     }
 
@@ -616,7 +711,7 @@ Heap::InternalClass *InternalClass::frozen()
         attrs.setConfigurable(false);
         f->propertyData.set(i, attrs);
     }
-    f->isFrozen = true;
+    f->flags |= Frozen;
 
     t.lookup = f;
     return f;
@@ -640,7 +735,7 @@ InternalClass *InternalClass::cryopreserved()
 
 bool InternalClass::isImplicitlyFrozen() const
 {
-    if (isFrozen)
+    if (isFrozen())
         return true;
 
     for (uint i = 0; i < size; ++i) {
@@ -656,7 +751,7 @@ bool InternalClass::isImplicitlyFrozen() const
 
 Heap::InternalClass *InternalClass::asProtoClass()
 {
-    if (isUsedAsProto)
+    if (isUsedAsProto())
         return this;
 
     Transition temp = { { PropertyKey::invalid() }, nullptr, Transition::ProtoClass };
@@ -665,7 +760,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);
@@ -685,7 +780,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);
 
@@ -698,6 +793,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 03ad7b827e..92ed5a9447 100644
--- a/src/qml/jsruntime/qv4internalclass_p.h
+++ b/src/qml/jsruntime/qv4internalclass_p.h
@@ -172,7 +172,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 *) {}
@@ -197,7 +197,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);
@@ -290,24 +290,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
@@ -323,10 +332,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 2bbc6dee5a..4674b750ed 100644
--- a/src/qml/jsruntime/qv4object.cpp
+++ b/src/qml/jsruntime/qv4object.cpp
@@ -61,17 +61,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
@@ -958,7 +993,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)
@@ -982,7 +1017,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 ba6829fb88..e30903239b 100644
--- a/src/qml/jsruntime/qv4propertykey_p.h
+++ b/src/qml/jsruntime/qv4propertykey_p.h
@@ -51,6 +51,7 @@
 //
 
 #include <private/qv4global_p.h>
+#include <QtCore/qhashfunctions.h>
 
 QT_BEGIN_NAMESPACE
 
@@ -145,6 +146,10 @@ 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; }
+    inline friend uint qHash(const PropertyKey &key, uint seed) noexcept
+    {
+        return QT_PREPEND_NAMESPACE(qHash)(key.val, seed);
+    }
 };
 
 }