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>

7 files changed, 210 insertions, 64 deletions

diff --git a/src/qml/jsruntime/qv4engine.cpp b/src/qml/jsruntime/qv4engine.cpp
index 200d5b0e3f..6ad8d2742b 100644
--- a/src/qml/jsruntime/qv4engine.cpp
+++ b/src/qml/jsruntime/qv4engine.cpp
@@ -2185,7 +2185,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 cc839d5239..c22a88f007 100644
--- a/src/qml/jsruntime/qv4internalclass.cpp
+++ b/src/qml/jsruntime/qv4internalclass.cpp
@@ -114,7 +114,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());
@@ -201,6 +201,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);
@@ -209,13 +216,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
@@ -236,10 +236,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);
@@ -301,7 +299,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();
@@ -317,7 +407,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);
@@ -330,7 +420,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);
     }
@@ -339,7 +430,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)
@@ -349,7 +441,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;
@@ -363,8 +455,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)
@@ -385,12 +476,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};
@@ -399,7 +492,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);
@@ -436,7 +529,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) {
@@ -489,21 +582,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;
     }
 
@@ -511,7 +606,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())
@@ -520,7 +615,7 @@ Heap::InternalClass *InternalClass::sealed()
             s->propertyData.set(i, attrs);
         }
     }
-    s->isSealed = true;
+    s->flags |= Sealed;
 
     t.lookup = s;
     return s;
@@ -528,14 +623,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;
     }
 
@@ -552,7 +647,7 @@ Heap::InternalClass *InternalClass::frozen()
         attrs.setConfigurable(false);
         f->propertyData.set(i, attrs);
     }
-    f->isFrozen = true;
+    f->flags |= Frozen;
 
     t.lookup = f;
     return f;
@@ -576,7 +671,7 @@ InternalClass *InternalClass::cryopreserved()
 
 bool InternalClass::isImplicitlyFrozen() const
 {
-    if (isFrozen)
+    if (isFrozen())
         return true;
 
     for (uint i = 0; i < size; ++i) {
@@ -592,7 +687,7 @@ bool InternalClass::isImplicitlyFrozen() const
 
 Heap::InternalClass *InternalClass::asProtoClass()
 {
-    if (isUsedAsProto)
+    if (isUsedAsProto())
         return this;
 
     Transition temp = { { PropertyKey::invalid() }, nullptr, Transition::ProtoClass };
@@ -601,7 +696,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);
@@ -621,7 +716,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);
 
@@ -634,6 +729,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 c9667ed368..d9a22dfc2c 100644
--- a/src/qml/jsruntime/qv4internalclass_p.h
+++ b/src/qml/jsruntime/qv4internalclass_p.h
@@ -136,7 +136,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 *) {}
@@ -161,7 +161,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);
@@ -252,24 +252,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
@@ -285,10 +294,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 021872b7ad..3b34854ae1 100644
--- a/src/qml/jsruntime/qv4qobjectwrapper.cpp
+++ b/src/qml/jsruntime/qv4qobjectwrapper.cpp
@@ -753,7 +753,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);