Add a unique id to InternalClass that describes it's total state

So far the InternalClass only did describe the state of the class
itself, but it wouldn't change if some of the underlying
objects in the prototype chain changed. This now fixes that and
introduces a unique ID that completely describes the state of
the object including all it's prototypes.

This opens up for optimizing lookups down to one branch and a
load, independent of the depth of the value inside the prototype
chain.

Change-Id: I0787e0e4710f2f6703b1d5e35996124b3db2d2da
Reviewed-by: Erik Verbruggen <erik.verbruggen@qt.io>

5 files changed, 82 insertions, 3 deletions

diff --git a/src/qml/jsruntime/qv4engine_p.h b/src/qml/jsruntime/qv4engine_p.h
index e143fe2de2..346f290feb 100644
--- a/src/qml/jsruntime/qv4engine_p.h
+++ b/src/qml/jsruntime/qv4engine_p.h
@@ -366,6 +366,8 @@ public:
     // bookkeeping.
     MultiplyWrappedQObjectMap *m_multiplyWrappedQObjects;
 
+    int internalClassIdCount = 0;
+
     ExecutionEngine();
     ~ExecutionEngine();
 
@@ -388,6 +390,8 @@ public:
         return static_cast<ExecutionContext *>(&currentStackFrame->jsFrame->context);
     }
 
+    int newInternalClassId() { return ++internalClassIdCount; }
+
     InternalClass *newInternalClass(const VTable *vtable, Object *prototype);
 
     Heap::Object *newObject();
diff --git a/src/qml/jsruntime/qv4internalclass.cpp b/src/qml/jsruntime/qv4internalclass.cpp
index 603da1df7b..d439884ca2 100644
--- a/src/qml/jsruntime/qv4internalclass.cpp
+++ b/src/qml/jsruntime/qv4internalclass.cpp
@@ -112,6 +112,7 @@ InternalClass::InternalClass(ExecutionEngine *engine)
     , size(0)
     , extensible(true)
 {
+    id = engine->newInternalClassId();
 }
 
 
@@ -127,8 +128,9 @@ InternalClass::InternalClass(const QV4::InternalClass &other)
     , m_frozen(0)
     , size(other.size)
     , extensible(other.extensible)
+    , isUsedAsProto(other.isUsedAsProto)
 {
-    Q_ASSERT(extensible);
+    id = engine->newInternalClassId();
 }
 
 static void insertHoleIntoPropertyData(Object *object, int idx)
@@ -213,7 +215,10 @@ InternalClass *InternalClass::changeMember(Identifier *identifier, PropertyAttri
 
 InternalClass *InternalClass::changePrototypeImpl(Heap::Object *proto)
 {
+    if (proto)
+        proto->setUsedAsProto();
     Q_ASSERT(prototype != proto);
+    Q_ASSERT(!proto || proto->internalClass->isUsedAsProto);
 
     Transition temp = { { nullptr }, 0, Transition::PrototypeChange };
     temp.prototype = proto;
@@ -237,6 +242,7 @@ InternalClass *InternalClass::changePrototypeImpl(Heap::Object *proto)
     }
 
     t.lookup = newClass;
+
     return newClass;
 }
 
@@ -389,7 +395,7 @@ void InternalClass::removeMember(Object *object, Identifier *id)
     Q_ASSERT(t.lookup);
 }
 
-uint QV4::InternalClass::find(const String *string)
+uint InternalClass::find(const String *string)
 {
     engine->identifierTable->identifier(string);
     const Identifier *id = string->d()->identifier;
@@ -449,6 +455,24 @@ InternalClass *InternalClass::propertiesFrozen() const
     return frozen;
 }
 
+InternalClass *InternalClass::asProtoClass()
+{
+    if (isUsedAsProto)
+        return this;
+
+    Transition temp = { { nullptr }, nullptr, Transition::ProtoClass };
+    Transition &t = lookupOrInsertTransition(temp);
+    if (t.lookup)
+        return t.lookup;
+
+    InternalClass *newClass = engine->newClass(*this);
+    newClass->isUsedAsProto = true;
+
+    t.lookup = newClass;
+    Q_ASSERT(t.lookup);
+    return newClass;
+}
+
 void InternalClass::destroy()
 {
     std::vector<InternalClass *> destroyStack;
@@ -478,6 +502,40 @@ void InternalClass::destroy()
     }
 }
 
+void InternalClass::updateProtoUsage(Heap::Object *o)
+{
+    Q_ASSERT(isUsedAsProto);
+    InternalClass *ic = engine->internalClasses[EngineBase::Class_Empty];
+    Q_ASSERT(!ic->prototype);
+
+    // only need to go two levels into the IC hierarchy, as prototype changes
+    // can only happen there
+    for (auto &t : ic->transitions) {
+        Q_ASSERT(t.lookup);
+        if (t.flags == InternalClassTransition::VTableChange) {
+            InternalClass *ic2 = t.lookup;
+            for (auto &t2 : ic2->transitions) {
+                if (t2.flags == InternalClassTransition::PrototypeChange &&
+                    t2.lookup->prototype == o)
+                    ic2->updateInternalClassIdRecursive();
+            }
+        } else if (t.flags == InternalClassTransition::PrototypeChange && t.lookup->prototype == o) {
+            ic->updateInternalClassIdRecursive();
+        }
+    }
+}
+
+void InternalClass::updateInternalClassIdRecursive()
+{
+    id = engine->newInternalClassId();
+    for (auto &t : transitions) {
+        Q_ASSERT(t.lookup);
+        t.lookup->updateInternalClassIdRecursive();
+    }
+}
+
+
+
 void InternalClassPool::markObjects(MarkStack *markStack)
 {
     InternalClass *ic = markStack->engine->internalClasses[EngineBase::Class_Empty];
diff --git a/src/qml/jsruntime/qv4internalclass_p.h b/src/qml/jsruntime/qv4internalclass_p.h
index df17074e72..546073dcf5 100644
--- a/src/qml/jsruntime/qv4internalclass_p.h
+++ b/src/qml/jsruntime/qv4internalclass_p.h
@@ -232,7 +232,8 @@ struct InternalClassTransition
         // range 0-0xff is reserved for attribute changes
         NotExtensible = 0x100,
         VTableChange = 0x200,
-        PrototypeChange = 0x201
+        PrototypeChange = 0x201,
+        ProtoClass = 0x202
     };
 
     bool operator==(const InternalClassTransition &other) const
@@ -243,6 +244,7 @@ struct InternalClassTransition
 };
 
 struct InternalClass : public QQmlJS::Managed {
+    int id = 0; // unique across the engine, gets changed also when proto chain changes
     ExecutionEngine *engine;
     const VTable *vtable;
     Heap::Object *prototype;
@@ -260,6 +262,7 @@ struct InternalClass : public QQmlJS::Managed {
 
     uint size;
     bool extensible;
+    bool isUsedAsProto = false;
 
     Q_REQUIRED_RESULT InternalClass *nonExtensible();
     Q_REQUIRED_RESULT InternalClass *changeVTable(const VTable *vt) {
@@ -293,12 +296,17 @@ struct InternalClass : public QQmlJS::Managed {
     Q_REQUIRED_RESULT InternalClass *frozen();
     Q_REQUIRED_RESULT InternalClass *propertiesFrozen() const;
 
+    Q_REQUIRED_RESULT InternalClass *asProtoClass();
+
     void destroy();
 
+    void updateProtoUsage(Heap::Object *o);
+
 private:
     Q_QML_EXPORT InternalClass *changeVTableImpl(const VTable *vt);
     Q_QML_EXPORT InternalClass *changePrototypeImpl(Heap::Object *proto);
     InternalClass *addMemberImpl(Identifier *identifier, PropertyAttributes data, uint *index);
+    void updateInternalClassIdRecursive();
     friend struct ExecutionEngine;
     InternalClass(ExecutionEngine *engine);
     InternalClass(const InternalClass &other);
diff --git a/src/qml/jsruntime/qv4object.cpp b/src/qml/jsruntime/qv4object.cpp
index 97296eb847..44414ad85a 100644
--- a/src/qml/jsruntime/qv4object.cpp
+++ b/src/qml/jsruntime/qv4object.cpp
@@ -60,6 +60,8 @@ DEFINE_OBJECT_VTABLE(Object);
 void Object::setInternalClass(InternalClass *ic)
 {
     d()->internalClass = ic;
+    if (ic->isUsedAsProto)
+        ic->updateProtoUsage(d());
     Q_ASSERT(ic && ic->vtable);
     uint nInline = d()->vtable()->nInlineProperties;
     if (ic->size <= nInline)
@@ -85,6 +87,11 @@ void Object::setProperty(uint index, const Property *p)
         setProperty(index + SetterOffset, p->set);
 }
 
+void Heap::Object::setUsedAsProto()
+{
+    internalClass = internalClass->asProtoClass();
+}
+
 bool Object::setPrototype(Object *proto)
 {
     Heap::Object *p = proto ? proto->d() : 0;
diff --git a/src/qml/jsruntime/qv4object_p.h b/src/qml/jsruntime/qv4object_p.h
index ff3ad7c0c6..0abb9b8fa5 100644
--- a/src/qml/jsruntime/qv4object_p.h
+++ b/src/qml/jsruntime/qv4object_p.h
@@ -129,6 +129,8 @@ DECLARE_EXPORTED_HEAP_OBJECT(Object, Base) {
         memberData->values.set(e, index, b);
     }
 
+    void setUsedAsProto();
+
     Heap::Object *prototype() const { return internalClass->prototype; }
 };