Fix backend node creation order using an initialization queue

Backend nodes should always be created from the top-most parent down
ensuring that every parent is created before its children. The original
way of creating backend nodes by calling _q_postConstructorInit
in a deferred manner from the QNode constructor breaks this because
backend node creation happens in the order that the nodes on the
front-end were created. This was often incorrect when reparenting
newly created nodes.

Fix by creating a queue of nodes needing a _q_postConstructorInit call
and only adding nodes to the queue if one of their ancestors is not
already in the queue. This ensures that _q_postConstructorInit is only
called for the top-most node in any subtree.  This behavior exactly
matches the creation behavior when building a subtree and reparenting
it to a node with a backend.

Doing silly things like creating a node with a parent that has a backend
then immediately reparenting is now safe. After this patch, it should
be safe to assume that backend nodes can always find their backend
parent.

Adding only the top-most nodes to the queue and processing the entire
queue at one time also ensures that all creation events get sent in
the same batch. This fixes the problem of having backend nodes referring
to other backend nodes that haven't been created yet.

Task-number: QTBUG-74106
Task-number: QTBUG-73905
Change-Id: Idcf38d6c3164f6be4394a3b25554547414061059
Reviewed-by: Paul Lemire <paul.lemire@kdab.com>

2 files changed, 95 insertions, 2 deletions

diff --git a/src/core/nodes/qnode.cpp b/src/core/nodes/qnode.cpp
index c2373b805..900c3f8ce 100644
--- a/src/core/nodes/qnode.cpp
+++ b/src/core/nodes/qnode.cpp
@@ -101,7 +101,7 @@ void QNodePrivate::init(QNode *parent)
     Q_Q(QNode);
     if (m_scene) {
         // schedule the backend notification and scene registering -> set observers through scene
-        QMetaObject::invokeMethod(q, "_q_postConstructorInit", Qt::QueuedConnection);
+        m_scene->postConstructorInit()->addNode(q);
     }
 }
 
@@ -165,7 +165,7 @@ void QNodePrivate::notifyDestructionChangesAndRemoveFromScene()
  *
  * Sends a QNodeCreatedChange event to the aspects and then also notifies the
  * parent backend node of its new child. This is called in a deferred manner
- * by the QNodePrivate::init() method to notify the backend of newly created
+ * by NodePostConstructorInit::processNodes to notify the backend of newly created
  * nodes with a parent that is already part of the scene.
  *
  * Also notify the scene of this node, so it may set it's change arbiter.
@@ -873,6 +873,12 @@ void QNode::setParent(QNode *parent)
     if (parentNode() == parent &&
             ((parent != nullptr && d->m_parentId == parentNode()->id()) || parent == nullptr))
         return;
+
+    // remove ourself from postConstructorInit queue. The call to _q_setParentHelper
+    // will take care of creating the backend node if necessary depending on new parent.
+    if (d->m_scene)
+        d->m_scene->postConstructorInit()->removeNode(this);
+
     d->_q_setParentHelper(parent);
 
     // Block notifications as we want to let the _q_setParentHelper
@@ -1132,6 +1138,75 @@ const QMetaObject *QNodePrivate::findStaticMetaObject(const QMetaObject *metaObj
     return lastStaticMetaobject;
 }
 
+/*!
+ * \internal
+ *
+ * NodePostConstructorInit handles calling QNode::_q_postConstructorInit for
+ * all nodes. By keeping track of nodes that need initialization we can
+ * create them all together ensuring they get sent to the backend in a single
+ * batch.
+ */
+NodePostConstructorInit::NodePostConstructorInit(QObject *parent)
+    : QObject(parent)
+    , m_requestedProcessing(false)
+{
+}
+
+NodePostConstructorInit::~NodePostConstructorInit() {}
+
+/*!
+ * \internal
+ *
+ * Add a node to the list of nodes needing a call to _q_postConstructorInit
+ * We only add the node if it does not have an ancestor already in the queue
+ * because initializing the ancestor will initialize all it's children.
+ * This ensures that all backend nodes are created from the top-down, with
+ * all parents created before their children
+ *
+ */
+void NodePostConstructorInit::addNode(QNode *node)
+{
+    Q_ASSERT(node);
+    QNode *nextNode = node;
+    while (nextNode != nullptr && !m_nodesToConstruct.contains(QNodePrivate::get(nextNode)))
+        nextNode = nextNode->parentNode();
+
+    if (!nextNode) {
+        m_nodesToConstruct.append(QNodePrivate::get(node));
+        if (!m_requestedProcessing){
+            QMetaObject::invokeMethod(this, "processNodes", Qt::QueuedConnection);
+            m_requestedProcessing = true;
+        }
+    }
+}
+
+/*!
+ * \internal
+ *
+ * Remove a node from the queue. This will ensure none of its
+ * children get initialized
+ */
+void NodePostConstructorInit::removeNode(QNode *node)
+{
+    Q_ASSERT(node);
+    m_nodesToConstruct.removeAll(QNodePrivate::get(node));
+}
+
+/*!
+ * \internal
+ *
+ * call _q_postConstructorInit for all nodes in the queue
+ * and clear the queue
+ */
+void NodePostConstructorInit::processNodes()
+{
+    m_requestedProcessing = false;
+    while (!m_nodesToConstruct.empty()) {
+        auto node = m_nodesToConstruct.takeFirst();
+        node->_q_postConstructorInit();
+    }
+}
+
 } // namespace Qt3DCore
 
 QT_END_NAMESPACE
diff --git a/src/core/nodes/qnode_p.h b/src/core/nodes/qnode_p.h
index 6ffb19ce8..8b43c2695 100644
--- a/src/core/nodes/qnode_p.h
+++ b/src/core/nodes/qnode_p.h
@@ -60,6 +60,7 @@
 #include <Qt3DCore/private/qobservableinterface_p.h>
 #include <Qt3DCore/private/qt3dcore_global_p.h>
 #include <QtCore/private/qobject_p.h>
+#include <QQueue>
 
 QT_BEGIN_NAMESPACE
 
@@ -174,6 +175,23 @@ private:
     QHash<QNode *, QMetaObject::Connection> m_destructionConnections;
 };
 
+class NodePostConstructorInit : public QObject
+{
+    Q_OBJECT
+public:
+    NodePostConstructorInit(QObject *parent = nullptr);
+    virtual ~NodePostConstructorInit();
+    void removeNode(QNode *node);
+    void addNode(QNode *node);
+
+private Q_SLOTS:
+    void processNodes();
+
+private:
+    QQueue<QNodePrivate *> m_nodesToConstruct;
+    bool m_requestedProcessing;
+};
+
 } // namespace Qt3DCore
 
 QT_END_NAMESPACE