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>

6 files changed, 187 insertions, 3 deletions

diff --git a/src/core/changes/qpropertynodeaddedchange.cpp b/src/core/changes/qpropertynodeaddedchange.cpp
index 865de2731..347d7f188 100644
--- a/src/core/changes/qpropertynodeaddedchange.cpp
+++ b/src/core/changes/qpropertynodeaddedchange.cpp
@@ -85,7 +85,7 @@ QPropertyNodeAddedChange::QPropertyNodeAddedChange(QNodeId subjectId, QNode *nod
     // loop will still be blocked. So force it here and we catch this
     // eventuality in the _q_postConstructorInit() function so that we
     // do not repeat the creation and new child scene change events.
-    QNodePrivate::get(node)->_q_postConstructorInit();
+    QNodePrivate::get(node)->_q_ensureBackendNodeCreated();
 }
 
 /*! \internal */
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
diff --git a/src/core/qscene.cpp b/src/core/qscene.cpp
index b5895c7aa..9624aec64 100644
--- a/src/core/qscene.cpp
+++ b/src/core/qscene.cpp
@@ -58,6 +58,7 @@ public:
         : m_engine(engine)
         , m_arbiter(nullptr)
         , m_rootNode(nullptr)
+        , m_postConstructorInit(new NodePostConstructorInit)
     {
     }
 
@@ -68,6 +69,7 @@ public:
     QHash<QObservableInterface *, QNodeId> m_observableToUuid;
     QHash<QNodeId, QScene::NodePropertyTrackData> m_nodePropertyTrackModeLookupTable;
     QLockableObserverInterface *m_arbiter;
+    QScopedPointer<NodePostConstructorInit> m_postConstructorInit;
     mutable QReadWriteLock m_lock;
     mutable QReadWriteLock m_nodePropertyTrackModeLock;
     QNode *m_rootNode;
@@ -247,6 +249,12 @@ void QScene::removePropertyTrackDataForNode(QNodeId nodeId)
     d->m_nodePropertyTrackModeLookupTable.remove(nodeId);
 }
 
+NodePostConstructorInit *QScene::postConstructorInit() const
+{
+    Q_D(const QScene);
+    return d->m_postConstructorInit.get();
+}
+
 void QScene::setRootNode(QNode *root)
 {
     Q_D(QScene);
diff --git a/src/core/qscene_p.h b/src/core/qscene_p.h
index aaa8d9e92..1de7e3d4d 100644
--- a/src/core/qscene_p.h
+++ b/src/core/qscene_p.h
@@ -64,6 +64,7 @@ namespace Qt3DCore {
 
 class QScenePrivate;
 class QAspectEngine;
+class NodePostConstructorInit;
 
 typedef QList<QObservableInterface *> QObservableList;
 
@@ -106,6 +107,8 @@ public:
     void setPropertyTrackDataForNode(QNodeId id, const NodePropertyTrackData &data);
     void removePropertyTrackDataForNode(QNodeId id);
 
+    NodePostConstructorInit* postConstructorInit() const;
+
 private:
     Q_DECLARE_PRIVATE(QScene)
     QScopedPointer<QScenePrivate> d_ptr;
diff --git a/tests/auto/core/nodes/tst_nodes.cpp b/tests/auto/core/nodes/tst_nodes.cpp
index 193d88c83..dad66c5d5 100644
--- a/tests/auto/core/nodes/tst_nodes.cpp
+++ b/tests/auto/core/nodes/tst_nodes.cpp
@@ -73,6 +73,7 @@ private slots:
     void checkParentChangeToNull();
     void checkParentChangeToOtherParent();
     void checkParentChangeFromExistingBackendParentToNewlyCreatedParent();
+    void checkBackendNodesCreatedFromTopDown();   //QTBUG-74106
 
     void removingSingleChildNodeFromNode();
     void removingMultipleChildNodesFromNode();
@@ -902,6 +903,85 @@ void tst_Nodes::checkParentChangeFromExistingBackendParentToNewlyCreatedParent()
     }
 }
 
+//Test creation changes happen for an entire subtree at once, starting at the top
+// so that parents are always created before their children. Even if the front-end
+// nodes are constructed in a different order.
+void tst_Nodes::checkBackendNodesCreatedFromTopDown()
+{
+    // GIVEN
+    Qt3DCore::QScene scene;
+    ObserverSpy spy;
+    QScopedPointer<MyQNode> root(new MyQNode());
+    root->setArbiterAndScene(&spy, &scene);
+    QScopedPointer<Qt3DCore::QNode> parentWithBackend(new MyQNode(root.data()));
+
+    // create parent backend node
+    QCoreApplication::processEvents();
+    QVERIFY(Qt3DCore::QNodePrivate::get(parentWithBackend.get())->m_hasBackendNode);
+
+    // WHEN -> creating 3 nodes and setting one as a property on the other
+    //         child2 is set as property on child1, but is created AFTER child1
+    spy.events.clear();
+    MyQNode *dummyParent(new MyQNode(parentWithBackend.data()));
+    MyQNode *child1(new MyQNode(parentWithBackend.data()));
+    MyQNode *child2(new MyQNode(dummyParent));
+    child2->setNodeProperty(child1);
+
+    // THEN - we should have no events because the new nodes have no backend yet
+    QCOMPARE(spy.events.count(), 0);
+
+    // WHEN - create the backend nodes
+    QCoreApplication::processEvents();
+
+    // THEN
+    QVERIFY(dummyParent->parent() == parentWithBackend.data());
+    QVERIFY(child1->parent() == parentWithBackend.data());
+    QVERIFY(child2->parent() == dummyParent);
+
+    // THEN
+    QCOMPARE(spy.events.size(), 5);
+    // 2 node creation change for dummyParent subtree (dummyParent and child2)
+    // 1 node added to children change (dummyParent to parent)
+    // 1 node created change for child1
+    // 1 node added to children change (child1 to parent)
+
+    {
+        // 1st event: dummyParent creation
+        const auto event1 = spy.events.takeFirst().change().dynamicCast<Qt3DCore::QNodeCreatedChangeBase>();
+        QVERIFY(!event1.isNull());
+        QCOMPARE(event1->type(), Qt3DCore::NodeCreated);
+        QCOMPARE(event1->parentId(), parentWithBackend->id());
+        QCOMPARE(event1->subjectId(), dummyParent->id());
+
+        // 2nd event: child2 creation (even though we constructed child1 first)
+        const auto event2 = spy.events.takeFirst().change().dynamicCast<Qt3DCore::QNodeCreatedChangeBase>();
+        QVERIFY(!event2.isNull());
+        QCOMPARE(event2->type(), Qt3DCore::NodeCreated);
+        QCOMPARE(event2->parentId(), dummyParent->id());
+        QCOMPARE(event2->subjectId(), child2->id());
+
+        // 3rd event: dummyParent added to parent
+        const auto event3 = spy.events.takeFirst().change().dynamicCast<Qt3DCore::QPropertyNodeAddedChange>();
+        QCOMPARE(event3->type(), Qt3DCore::PropertyValueAdded);
+        QCOMPARE(event3->addedNodeId(), dummyParent->id());
+        QCOMPARE(event3->subjectId(), parentWithBackend->id());
+
+        // 4th event: child1 creation
+        const auto event4 = spy.events.takeFirst().change().dynamicCast<Qt3DCore::QNodeCreatedChangeBase>();
+        QVERIFY(!event4.isNull());
+        QCOMPARE(event4->type(), Qt3DCore::NodeCreated);
+        QCOMPARE(event4->parentId(), parentWithBackend->id());
+        QCOMPARE(event4->subjectId(), child1->id());
+
+        // 5th event: child 1 added to parent
+        const auto event5 = spy.events.takeFirst().change().dynamicCast<Qt3DCore::QPropertyNodeAddedChange>();
+        QCOMPARE(event5->type(), Qt3DCore::PropertyValueAdded);
+        QCOMPARE(event5->addedNodeId(), child1->id());
+        QCOMPARE(event5->subjectId(), parentWithBackend->id());
+    }
+}
+
+
 void tst_Nodes::removingSingleChildNodeFromNode()
 {
     // GIVEN