Simplify the safeguarding logic in notify()

The logic in notify() was doing quite a bit more work than
it needed to. By inserting a dummy node after the current one instead of
replacing it, we can avoid half of the data shuffling that has been
happening and also don't need a back pointer when executing the
notification.

Also avoid calling a semi expensive destructor of QPropertyObserver.

Reduces the overhead of notify() by ~30%.

Change-Id: I7ce16bcf9cd9c4368c18bf875fc959223452fd4f
Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
(cherry picked from commit e8ef871e3522f340b4efe32382af7e35ef908665)
Reviewed-by: Qt Cherry-pick Bot <cherrypick_bot@qt-project.org>

3 files changed, 80 insertions, 118 deletions

diff --git a/src/corelib/kernel/qproperty.cpp b/src/corelib/kernel/qproperty.cpp
index 07658cb9de..6ccf8d7b8f 100644
--- a/src/corelib/kernel/qproperty.cpp
+++ b/src/corelib/kernel/qproperty.cpp
@@ -399,10 +399,6 @@ void QPropertyObserver::setSource(const QPropertyBindingData &property)
 
 QPropertyObserver::~QPropertyObserver()
 {
-    if (next.tag() == ActivelyExecuting) {
-        if (nodeState)
-            *nodeState = nullptr;
-    }
     QPropertyObserverPointer d{this};
     d.unlink();
 }
@@ -416,8 +412,6 @@ QPropertyObserver::QPropertyObserver(QPropertyObserver &&other) noexcept
         next->prev = &next;
     if (prev)
         prev.setPointer(this);
-    if (next.tag() == ActivelyExecuting)
-        *nodeState = this;
 }
 
 QPropertyObserver &QPropertyObserver::operator=(QPropertyObserver &&other) noexcept
@@ -436,8 +430,6 @@ QPropertyObserver &QPropertyObserver::operator=(QPropertyObserver &&other) noexc
         next->prev = &next;
     if (prev)
         prev.setPointer(this);
-    if (next.tag() == ActivelyExecuting)
-        *nodeState = this;
 
     return *this;
 }
@@ -456,21 +448,21 @@ void QPropertyObserverPointer::unlink()
 
 void QPropertyObserverPointer::setChangeHandler(QPropertyObserver::ChangeHandler changeHandler)
 {
-    Q_ASSERT(ptr->next.tag() != QPropertyObserver::ActivelyExecuting);
+    Q_ASSERT(ptr->next.tag() != QPropertyObserver::ObserverIsPlaceholder);
     ptr->changeHandler = changeHandler;
     ptr->next.setTag(QPropertyObserver::ObserverNotifiesChangeHandler);
 }
 
 void QPropertyObserverPointer::setAliasedProperty(QUntypedPropertyData *property)
 {
-    Q_ASSERT(ptr->next.tag() != QPropertyObserver::ActivelyExecuting);
+    Q_ASSERT(ptr->next.tag() != QPropertyObserver::ObserverIsPlaceholder);
     ptr->aliasedPropertyData = property;
     ptr->next.setTag(QPropertyObserver::ObserverNotifiesAlias);
 }
 
 void QPropertyObserverPointer::setBindingToMarkDirty(QPropertyBindingPrivate *binding)
 {
-    Q_ASSERT(ptr->next.tag() != QPropertyObserver::ActivelyExecuting);
+    Q_ASSERT(ptr->next.tag() != QPropertyObserver::ObserverIsPlaceholder);
     ptr->bindingToMarkDirty = binding;
     ptr->next.setTag(QPropertyObserver::ObserverNotifiesBinding);
 }
@@ -480,55 +472,26 @@ void QPropertyObserverPointer::setBindingToMarkDirty(QPropertyBindingPrivate *bi
  QPropertyObserverNodeProtector is a RAII wrapper which takes care of the internal switching logic
  for QPropertyObserverPointer::notify (described ibidem)
 */
-template <QPropertyObserver::ObserverTag tag>
 struct [[nodiscard]] QPropertyObserverNodeProtector {
-    QPropertyObserver m_placeHolder;
-    QPropertyObserver *&m_observer;
-    union {
-        QPropertyBindingPrivate *m_binding;
-        QPropertyObserver::ChangeHandler m_changeHandler;
-    };
-    QPropertyObserverNodeProtector(QPropertyObserver *&observer)
-        : m_observer(observer)
+    QPropertyObserverBase m_placeHolder;
+    QPropertyObserverNodeProtector(QPropertyObserver *observer)
     {
-        static_assert(tag == QPropertyObserver::ObserverNotifiesBinding ||
-                 tag == QPropertyObserver::ObserverNotifiesChangeHandler);
-        if constexpr (tag == QPropertyObserver::ObserverNotifiesBinding)
-            m_binding = m_observer->bindingToMarkDirty;
-        else
-            m_changeHandler = m_observer->changeHandler;
-        switchNodes(m_placeHolder, m_observer);
-        m_observer->nodeState = &m_observer;
-        m_observer->next.setTag(QPropertyObserver::ActivelyExecuting);
-        m_placeHolder.next.setTag(QPropertyObserver::ActivelyExecuting);
+        // insert m_placeholder after observer into the linked list
+        QPropertyObserver *next = observer->next.data();
+        m_placeHolder.next = next;
+        observer->next = static_cast<QPropertyObserver *>(&m_placeHolder);
+        if (next)
+            next->prev = &m_placeHolder.next;
+        m_placeHolder.prev = &observer->next;
+        m_placeHolder.next.setTag(QPropertyObserver::ObserverIsPlaceholder);
     }
 
+    QPropertyObserver *next() const { return m_placeHolder.next.data(); }
+
     ~QPropertyObserverNodeProtector() {
-        if (m_observer) {
-            if constexpr (tag == QPropertyObserver::ObserverNotifiesBinding)
-                m_observer->bindingToMarkDirty = m_binding;
-            else
-                m_observer->changeHandler = m_changeHandler;
-            switchNodes(*m_observer, &m_placeHolder);
-            m_observer->next.setTag(tag);
-        }
-        // set tag to a safer value where we don't execute anything in the dtor
-        m_placeHolder.next.setTag(QPropertyObserver::ObserverNotifiesChangeHandler);
+        QPropertyObserverPointer d{static_cast<QPropertyObserver *>(&m_placeHolder)};
+        d.unlink();
     }
-
-    /*!
-      \internal
-      replaces a node \a observer in the list with another node \a placeholder which must not be in the list
-     */
-    static void switchNodes(QPropertyObserver &placeHolder, QPropertyObserver *observer)  {
-        placeHolder.next = std::exchange(observer->next, {});
-        placeHolder.prev = std::exchange(observer->prev, {});
-        if (placeHolder.next) {
-            placeHolder.next->prev = &placeHolder.next;
-        }
-        if (placeHolder.prev)
-            placeHolder.prev.setPointer(&placeHolder);
-    };
 };
 
 /*! \internal
@@ -540,7 +503,7 @@ struct [[nodiscard]] QPropertyObserverNodeProtector {
   ObserverNotifiesChangeHandler case would not work. Thus we instead pass the knowledge of
   whether the value has changed we obtained when evaluating the binding eagerly along
  */
-void QPropertyObserverPointer::notify(QPropertyBindingPrivate *triggeringBinding, QUntypedPropertyData *propertyDataPtr,bool alreadyKnownToHaveChanged)
+void QPropertyObserverPointer::notify(QPropertyBindingPrivate *triggeringBinding, QUntypedPropertyData *propertyDataPtr, bool alreadyKnownToHaveChanged)
 {
     bool knownIfPropertyChanged = alreadyKnownToHaveChanged;
     bool propertyChanged = true;
@@ -552,56 +515,56 @@ void QPropertyObserverPointer::notify(QPropertyBindingPrivate *triggeringBinding
      * However, complication arise due to the fact that the triggered operations might modify the list,
      * which includes deletion and move of the current and next nodes.
      * Therefore, we take a few safety precautions:
-     * 1. Before executing any action which might modify the list, we replace the actual node in the list with
-     *    a placeholder node. As that one is stack allocated and owned by us, we can rest assured that it is
+     * 1. Before executing any action which might modify the list, we insert a placeholder node after the current node.
+     *    As that one is stack allocated and owned by us, we can rest assured that it is
      *    still there after the action has executed, and placeHolder->next points to the actual next node in the list.
      *    Note that taking next at the beginning of the loop does not work, as the execuated action might either move
      *    or delete that node.
-     * 2. To properly handle deletion or moves of the real current node, we store a pointer to a pointer to itself in
-     *    its nodeState. Whenever the node is reallocated and moved, we update that pointer to point to its new
-     *    location. If the node is actually deleted, we set it to nullptr.
-     * 3. After the triggered action has finished, we can use that information to restore the list to contain the actual
-     *    node again. We either switch the nodes with the real nodes current location, or, if the real node has been
-     *    deleted, we simply unlink the temporary node.
+     * 2. After the triggered action has finished, we can use the next pointer in the placeholder node as a safe way to
+     *    retrieve the next node.
+     * 3. Some care needs to be taken to avoid infinite recursion with change handlers, so we add an extra test there, that
+     *    checks whether we're already have the same change handler in our call stack. This can be done by checking whether
+     *    the node after the current one is a placeholder node.
      */
     while (observer) {
-        QPropertyObserver *next = nullptr;
+        QPropertyObserver *next = observer->next.data();
+
         char preventBug[1] = {'\0'}; // QTBUG-87245
         Q_UNUSED(preventBug);
-        switch (observer->next.tag()) {
+        switch (QPropertyObserver::ObserverTag(observer->next.tag())) {
         case QPropertyObserver::ObserverNotifiesChangeHandler:
-            if (auto handlerToCall = observer->changeHandler) {
-                // both evaluateIfDirtyAndReturnTrueIfValueChanged and handlerToCall might modify the list
-                QPropertyObserverNodeProtector<QPropertyObserver::ObserverNotifiesChangeHandler> protector(observer);
-                if (!knownIfPropertyChanged && triggeringBinding) {
-                    knownIfPropertyChanged = true;
-                    propertyChanged = triggeringBinding->evaluateIfDirtyAndReturnTrueIfValueChanged(propertyDataPtr);
-                }
-                if (!propertyChanged)
-                    return;
-                handlerToCall(observer, propertyDataPtr);
-                next = protector.m_placeHolder.next.data();
-            } else {
-                next = observer->next.data();
+        {
+            auto handlerToCall = observer->changeHandler;
+            // prevent recursion
+            if (next && next->next.tag() == QPropertyObserver::ObserverIsPlaceholder) {
+                observer = next->next.data();
+                continue;
             }
+            // both evaluateIfDirtyAndReturnTrueIfValueChanged and handlerToCall might modify the list
+            QPropertyObserverNodeProtector protector(observer);
+            if (!knownIfPropertyChanged && triggeringBinding) {
+                knownIfPropertyChanged = true;
+                propertyChanged = triggeringBinding->evaluateIfDirtyAndReturnTrueIfValueChanged(propertyDataPtr);
+            }
+            if (!propertyChanged)
+                return;
+            handlerToCall(observer, propertyDataPtr);
+            next = protector.next();
             break;
+        }
         case QPropertyObserver::ObserverNotifiesBinding:
-            if (auto bindingToMarkDirty =  observer->bindingToMarkDirty) {
-                QPropertyObserverNodeProtector<QPropertyObserver::ObserverNotifiesBinding> protector(observer);
-                bindingToMarkDirty->markDirtyAndNotifyObservers();
-                next = protector.m_placeHolder.next.data();
-            } else {
-                next = observer->next.data();
-            }
+        {
+            auto bindingToMarkDirty =  observer->bindingToMarkDirty;
+            QPropertyObserverNodeProtector protector(observer);
+            bindingToMarkDirty->markDirtyAndNotifyObservers();
+            next = protector.next();
             break;
+        }
         case QPropertyObserver::ObserverNotifiesAlias:
-            next = observer->next.data();
             break;
-        case QPropertyObserver::ActivelyExecuting:
+        case QPropertyObserver::ObserverIsPlaceholder:
             // recursion is already properly handled somewhere else
-            return;
-        default:
-            Q_UNREACHABLE();
+            break;
         }
         observer = next;
     }
diff --git a/src/corelib/kernel/qproperty.h b/src/corelib/kernel/qproperty.h
index d612486e2c..058e265934 100644
--- a/src/corelib/kernel/qproperty.h
+++ b/src/corelib/kernel/qproperty.h
@@ -205,8 +205,9 @@ namespace Qt {
 
 struct QPropertyObserverPrivate;
 struct QPropertyObserverPointer;
+class QPropertyObserver;
 
-class Q_CORE_EXPORT QPropertyObserver
+class QPropertyObserverBase
 {
 public:
     // Internal
@@ -214,10 +215,33 @@ public:
         ObserverNotifiesBinding, // observer was installed to notify bindings that obsverved property changed
         ObserverNotifiesChangeHandler, // observer is a change handler, which runs on every change
         ObserverNotifiesAlias, // used for QPropertyAlias
-        ActivelyExecuting  // the observer is currently evaluated in QPropertyObserver::notifyObservers or its
-                           // placeholder. We only can store 4 different values, therefore those two conflate
+        ObserverIsPlaceholder  // the observer before this one is currently evaluated in QPropertyObserver::notifyObservers.
     };
+protected:
+    using ChangeHandler = void (*)(QPropertyObserver*, QUntypedPropertyData *);
+
+private:
+    friend struct QPropertyObserverNodeProtector;
+    friend class QPropertyObserver;
+    friend struct QPropertyObserverPointer;
+    friend struct QPropertyBindingDataPointer;
+    friend class QPropertyBindingPrivate;
+
+    QTaggedPointer<QPropertyObserver, ObserverTag> next;
+    // prev is a pointer to the "next" element within the previous node, or to the "firstObserverPtr" if it is the
+    // first node.
+    QtPrivate::QTagPreservingPointerToPointer<QPropertyObserver, ObserverTag> prev;
+
+    union {
+        QPropertyBindingPrivate *bindingToMarkDirty = nullptr;
+        ChangeHandler changeHandler;
+        QUntypedPropertyData *aliasedPropertyData;
+    };
+};
 
+class Q_CORE_EXPORT QPropertyObserver : public QPropertyObserverBase
+{
+public:
     constexpr QPropertyObserver() = default;
     QPropertyObserver(QPropertyObserver &&other) noexcept;
     QPropertyObserver &operator=(QPropertyObserver &&other) noexcept;
@@ -229,7 +253,6 @@ public:
     void setSource(const QtPrivate::QPropertyBindingData &property);
 
 protected:
-    using ChangeHandler = void (*)(QPropertyObserver*, QUntypedPropertyData *);
     QPropertyObserver(ChangeHandler changeHandler);
     QPropertyObserver(QUntypedPropertyData *aliasedPropertyPtr);
 
@@ -240,26 +263,9 @@ protected:
 
 private:
 
-    QTaggedPointer<QPropertyObserver, ObserverTag> next;
-    // prev is a pointer to the "next" element within the previous node, or to the "firstObserverPtr" if it is the
-    // first node.
-    QtPrivate::QTagPreservingPointerToPointer<QPropertyObserver, ObserverTag> prev;
-
-    union {
-        QPropertyBindingPrivate *bindingToMarkDirty = nullptr;
-        ChangeHandler changeHandler;
-        QUntypedPropertyData *aliasedPropertyData;
-        QPropertyObserver **nodeState;
-    };
-
     QPropertyObserver(const QPropertyObserver &) = delete;
     QPropertyObserver &operator=(const QPropertyObserver &) = delete;
 
-    friend struct QPropertyObserverPointer;
-    friend struct QPropertyBindingDataPointer;
-    friend class QPropertyBindingPrivate;
-    template<ObserverTag>
-    friend struct QPropertyObserverNodeProtector;
 };
 
 template <typename Functor>
diff --git a/src/corelib/kernel/qproperty_p.h b/src/corelib/kernel/qproperty_p.h
index fb02af714b..1e4c7fc1b2 100644
--- a/src/corelib/kernel/qproperty_p.h
+++ b/src/corelib/kernel/qproperty_p.h
@@ -251,13 +251,6 @@ public:
     void clearDependencyObservers() {
         for (size_t i = 0; i < qMin(dependencyObserverCount, inlineDependencyObservers.size()); ++i) {
             QPropertyObserverPointer p{&inlineDependencyObservers[i]};
-            if (p.ptr->next.tag() == QPropertyObserver::ActivelyExecuting) {
-                *(p.ptr->nodeState) = nullptr;
-                p.ptr->nodeState = nullptr;
-
-                // set tag to "safer" value, as we return the same observer pointer from allocateDependencyObserver
-                p.ptr->next.setTag(QPropertyObserver::ObserverNotifiesChangeHandler);
-            }
             p.unlink();
         }
         if (heapObservers)