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>

1 files changed, 134 insertions, 36 deletions

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);
 }