Make QDomNodeList::It bidirectional only

The new (6.9) iterator for QDomNodeList was implemented as random access
iterator. The underlying structure of QDomNodeList is similar to a
linked list and therefore it is better suited for bidirectional
iterator.

This patch changes the iterator to a bidirectional iterator. Further the
tests are expanded because the new implementation uses more custom code.

Fixes: QTBUG-132527
Pick-to: 6.9
Change-Id: I796f445e0b883abc2aea613f1fed6f17c4d93dcd
Reviewed-by: Marc Mutz <[email protected]>
Reviewed-by: Volker Hilsheimer <[email protected]>

4 files changed, 180 insertions, 82 deletions

diff --git a/src/xml/dom/qdom.cpp b/src/xml/dom/qdom.cpp
index 3ef7bbe3e85..8259da2f1cb 100644
--- a/src/xml/dom/qdom.cpp
+++ b/src/xml/dom/qdom.cpp
@@ -656,8 +656,105 @@ void QDomNodeListPrivate::createList() const
     forEachNode([&](QDomNodePrivate *p){ list.append(p); });
 }
 
+/*! \internal
+
+    Checks if a node is valid and fulfills the requirements set during the
+    generation of this list, i.e. matching tag and matching URI.
+ */
+bool QDomNodeListPrivate::checkNode(QDomNodePrivate *p) const {
+    if (nsURI.isNull())
+        return p->isElement() && p->nodeName() == tagname;
+    else
+        return p->isElement() && p->name==tagname && p->namespaceURI==nsURI;
+};
+
+/*! \internal
+
+    Returns the next node item in the list. If the tagname or the URI are set,
+    the function iterates through the dom tree and returns node that match them.
+    If neither tag nor URI are set, the function iterates through a single level
+    in the tree and returns all nodes.
+
+    \sa forEachNode(), findPrevInOrder()
+ */
+QDomNodePrivate *QDomNodeListPrivate::findNextInOrder(QDomNodePrivate *p) const
+{
+    if (!p)
+        return p;
+
+    if (tagname.isNull()) {
+        if (p == node_impl)
+            return p->first;
+        else if (p && p->next)
+            return p->next;
+    }
+
+    if (p == node_impl) {
+        p = p->first;
+        if (checkNode(p))
+            return p;
+    }
+    while (p && p != node_impl) {
+        if (p->first) { // go down in the tree
+            p = p->first;
+        } else if (p->next) { // traverse the tree
+            p = p->next;
+        } else { // go up in the tree
+            p = p->parent();
+            while (p && p != node_impl && !p->next)
+                p = p->parent();
+            if (p && p != node_impl)
+                p = p->next;
+        }
+        if (checkNode(p))
+            return p;
+    }
+    return node_impl;
+}
+
+/*! \internal
+
+    Similar as findNextInOrder() but iterarating in the opposite order.
+
+    \sa forEachNode(), findNextInOrder()
+ */
+QDomNodePrivate *QDomNodeListPrivate::findPrevInOrder(QDomNodePrivate *p) const
+{
+    if (!p)
+        return p;
+
+    if (tagname.isNull() && p == node_impl)
+        return p->last;
+    if (tagname.isNull())
+        return p->prev;
+
+    // We end all the way down in the tree
+    // so that is where we have to start
+    if (p == node_impl) {
+        while (p->last)
+            p = p->last;
+        if (checkNode(p))
+            return p;
+    }
+
+    while (p) {
+        if (p->prev) {// traverse the tree backwards
+            p = p->prev;
+            // go mmediately down if an item has children
+            while (p->last)
+                p = p->last;
+        } else { // go up in the tree
+            p = p->parent();
+        }
+        if (checkNode(p))
+            return p;
+    }
+    return node_impl;
+}
+
 void QDomNodeListPrivate::forEachNode(qxp::function_ref<void(QDomNodePrivate*)> yield) const
 {
+    //TODO: simplify with findNextInList
     if (!node_impl)
         return;
 
@@ -910,8 +1007,8 @@ int QDomNodeList::noexceptLength() const noexcept
     \typedef QDomNodeList::const_reverse_iterator
     \since 6.9
 
-    Typedefs for an opaque class that implements a (reverse) random-access
-    iterator over a QDomNodeList.
+    Typedefs for an opaque class that implements a bidirectional iterator over
+    a QDomNodeList.
 
     \note QDomNodeList does not support modifying nodes in-place, so
     there is no mutable iterator.
@@ -920,7 +1017,6 @@ int QDomNodeList::noexceptLength() const noexcept
 /*!
     \typedef QDomNodeList::value_type
     \typedef QDomNodeList::difference_type
-    \typedef QDomNodeList::size_type
     \typedef QDomNodeList::reference
     \typedef QDomNodeList::const_reference
     \typedef QDomNodeList::pointer
@@ -954,6 +1050,27 @@ int QDomNodeList::noexceptLength() const noexcept
     there is no mutable iterator.
 */
 
+QDomNodeList::It::It(const QDomNodeListPrivate *lp, bool start) noexcept
+    : parent(lp)
+{
+    if (!lp || !lp->node_impl)
+        current = nullptr;
+    else if (start)
+        current = lp->findNextInOrder(lp->node_impl);
+    else
+        current = lp->node_impl;
+}
+
+QDomNodePrivate *QDomNodeList::It::findNextInOrder(const QDomNodeListPrivate *parent, QDomNodePrivate *current)
+{
+    return parent->findNextInOrder(current);
+}
+
+QDomNodePrivate *QDomNodeList::It::findPrevInOrder(const QDomNodeListPrivate *parent, QDomNodePrivate *current)
+{
+    return parent->findPrevInOrder(current);
+}
+
 /**************************************************************
  *
  * QDomNodePrivate
diff --git a/src/xml/dom/qdom.h b/src/xml/dom/qdom.h
index c7213074e25..8443293348e 100644
--- a/src/xml/dom/qdom.h
+++ b/src/xml/dom/qdom.h
@@ -244,74 +244,39 @@ private:
 
     class It
     {
-        const QDomNodeList *list;
-        int i;
+        const QDomNodeListPrivate *parent;
+        QDomNodePrivate *current;
 
         friend class QDomNodeList;
-        explicit constexpr It(const QDomNodeList *lp, int ii) noexcept : list(lp), i(ii) {}
+        friend class QDomNodeListPrivate;
+        Q_XML_EXPORT It(const QDomNodeListPrivate *lp, bool start) noexcept;
 
         friend constexpr bool comparesEqual(const It &lhs, const It &rhs)
-        { Q_ASSERT(lhs.list == rhs.list); return lhs.i == rhs.i; }
-        friend constexpr Qt::strong_ordering compareThreeWay(const It &lhs, const It &rhs)
-        { Q_ASSERT(lhs.list == rhs.list); return Qt::compareThreeWay(lhs.i, rhs.i); }
-        // macro variant does not exist: Q_DECLARE_STRONGLY_ORDERED_LITERAL_TYPE_NON_NOEXCEPT(It)
-        friend constexpr bool operator==(It lhs, It rhs) {
-            return comparesEqual(lhs, rhs);
-        }
-#ifdef __cpp_lib_three_way_comparison
-        friend constexpr std::strong_ordering operator<=>(It lhs, It rhs) {
-            return compareThreeWay(lhs, rhs);
-        }
-#else
-        friend constexpr bool operator!=(It lhs, It rhs) {
-            return !comparesEqual(lhs, rhs);
-        }
-        friend constexpr bool operator<(It lhs, It rhs) {
-            return is_lt(compareThreeWay(lhs, rhs));
-        }
-        friend constexpr bool operator<=(It lhs, It rhs) {
-            return is_lteq(compareThreeWay(lhs, rhs));
-        }
-        friend constexpr bool operator>(It lhs, It rhs) {
-            return is_gt(compareThreeWay(lhs, rhs));
-        }
-        friend constexpr bool operator>=(It lhs, It rhs) {
-            return is_gteq(compareThreeWay(lhs, rhs));
-        }
-#endif
+        { Q_ASSERT(lhs.parent == rhs.parent); return lhs.current == rhs.current; }
+        Q_DECLARE_EQUALITY_COMPARABLE_NON_NOEXCEPT(It);
+
+        Q_XML_EXPORT static QDomNodePrivate *findNextInOrder(const QDomNodeListPrivate *parent, QDomNodePrivate *current);
+        Q_XML_EXPORT static QDomNodePrivate *findPrevInOrder(const QDomNodeListPrivate *parent, QDomNodePrivate *current);
 
     public:
         // Rule Of Zero applies
         It() = default;
 
-        using iterator_category = std::random_access_iterator_tag;
+        using iterator_category = std::bidirectional_iterator_tag;
         using value_type = QDomNode;
         using element_type = const QDomNode;
         using difference_type = qptrdiff; // difference to [container.reqmts]
-        using size_type = int;            // difference to [container.reqmts]
         using reference = value_type;     // difference to [container.reqmts]
         using pointer = QtPrivate::ArrowProxy<reference>;
 
-        reference operator*() const { return list->item(i); }
+        reference operator*() const { return QDomNode(current); }
         pointer operator->() const { return { **this }; }
 
-        It &operator++() { ++i; return *this; }
+        It &operator++() { current = findNextInOrder(parent, current); return *this; }
         It operator++(int) { auto copy = *this; ++*this; return copy; }
 
-        It &operator--() { --i; return *this; }
+        It &operator--() { current = findPrevInOrder(parent, current); return *this; }
         It operator--(int) { auto copy = *this; --*this; return copy; }
-
-        It &operator+=(difference_type n) { i += n; return *this; }
-        friend It operator+(It it, difference_type n) { it += n; return it; }
-        friend It operator+(difference_type n, It it) { return it + n; }
-
-        It &operator-=(difference_type n) { i -= n; return *this; }
-        friend It operator-(It it, difference_type n) { it -= n; return it; }
-
-        friend difference_type operator-(It lhs, It rhs)
-        { Q_ASSERT(lhs.list == rhs.list); return lhs.i - rhs.i; }
-
-        reference operator[](difference_type n) const { return *(*this + n); }
     };
 
 public:
@@ -320,14 +285,13 @@ public:
 
     using value_type = It::value_type;
     using difference_type = It::difference_type;
-    using size_type = It::size_type;
     using reference = It::reference;
     using const_reference = reference;
     using pointer = It::pointer;
     using const_pointer = pointer;
 
-    [[nodiscard]] const_iterator begin()  const noexcept { return It{this, 0}; }
-    [[nodiscard]] const_iterator end()    const noexcept { return It{this, noexceptLength()}; }
+    [[nodiscard]] const_iterator begin()  const noexcept { return It{impl, true}; }
+    [[nodiscard]] const_iterator end()    const noexcept { return It{impl, false}; }
     [[nodiscard]] const_iterator cbegin() const noexcept { return begin(); }
     [[nodiscard]] const_iterator cend()   const noexcept { return end(); }
 
@@ -346,6 +310,7 @@ private:
     friend class QDomNode;
     friend class QDomElement;
     friend class QDomDocument;
+    friend class ::tst_QDom;
 };
 
 class Q_XML_EXPORT QDomDocumentType : public QDomNode
@@ -372,6 +337,7 @@ private:
     friend class QDomImplementation;
     friend class QDomDocument;
     friend class QDomNode;
+    friend class ::tst_QDom;
 };
 
 class Q_XML_EXPORT QDomDocument : public QDomNode
diff --git a/src/xml/dom/qdom_p.h b/src/xml/dom/qdom_p.h
index 2ead7a32e2d..1e51befef8e 100644
--- a/src/xml/dom/qdom_p.h
+++ b/src/xml/dom/qdom_p.h
@@ -148,6 +148,9 @@ public:
     bool operator==(const QDomNodeListPrivate &) const noexcept;
 
     void createList() const;
+    bool checkNode(QDomNodePrivate* p) const;
+    QDomNodePrivate *findNextInOrder(QDomNodePrivate* p) const;
+    QDomNodePrivate *findPrevInOrder(QDomNodePrivate* p) const;
     void forEachNode(qxp::function_ref<void(QDomNodePrivate*)> yield) const;
     bool maybeCreateList() const;
     QDomNodePrivate *item(int index);
diff --git a/tests/auto/xml/dom/qdom/tst_qdom.cpp b/tests/auto/xml/dom/qdom/tst_qdom.cpp
index a2e7ab9024b..8138de1fce3 100644
--- a/tests/auto/xml/dom/qdom/tst_qdom.cpp
+++ b/tests/auto/xml/dom/qdom/tst_qdom.cpp
@@ -1338,28 +1338,24 @@ void tst_QDom::domNodeListIterator()
     QVERIFY(doc.setContent(xml));
     QDomNodeList list = doc.childNodes().at(0).childNodes();
 
+    {
+        const QList<QDomNode> items(list.begin(), list.end());
+        QVERIFY(list.impl->list.isEmpty()); // we evaded maybeCreateList()
+
+        QCOMPARE(items.size(), list.size());
+        int i = 0;
+        for (const auto &item : items)
+            QCOMPARE(item, list.item(i++));
+    }
+
     auto listSize = list.size();
     QCOMPARE(listSize, 3);
 
     QCOMPARE_EQ(list.begin(), list.begin());
     QCOMPARE_EQ(list.end(), list.end());
     QCOMPARE_NE(list.begin(), list.end());
-    QCOMPARE_LT(list.begin(), list.end());
-    QCOMPARE_GE(list.end(), list.begin());
 
     auto it = list.begin();
-    it += listSize;
-    QVERIFY(it == list.end());
-    it -= listSize;
-    QVERIFY(it == list.begin());
-    it = it + listSize;
-    QVERIFY(it == list.end());
-    it = it - listSize;
-    QVERIFY(it == list.begin());
-    it = listSize + it;
-    QVERIFY(it == list.end());
-
-    it = list.begin();
     for (int i = 0; i < listSize; i++, it++)
         QVERIFY(*it == list.item(i));
     QVERIFY(it == list.end());
@@ -1407,28 +1403,24 @@ void tst_QDom::domNodeListReverseIterator()
     QVERIFY(doc.setContent(xml));
     QDomNodeList list = doc.childNodes().at(0).childNodes();
 
+    {
+        const QList<QDomNode> items(list.begin(), list.end());
+        QVERIFY(list.impl->list.isEmpty()); // we evaded maybeCreateList()
+
+        QCOMPARE(items.size(), list.size());
+        int i = 0;
+        for (const auto &item : items)
+            QCOMPARE(item, list.item(i++));
+    }
+
     auto listSize = list.size();
     QCOMPARE(listSize, 3);
 
     QCOMPARE_EQ(list.rbegin(), list.rbegin());
     QCOMPARE_EQ(list.rend(), list.rend());
     QCOMPARE_NE(list.rbegin(), list.rend());
-    QCOMPARE_LT(list.rbegin(), list.rend());
-    QCOMPARE_GE(list.rend(), list.rbegin());
 
     auto it = list.rbegin();
-    it += listSize;
-    QVERIFY(it == list.rend());
-    it -= listSize;
-    QVERIFY(it == list.rbegin());
-    it = it + listSize;
-    QVERIFY(it == list.rend());
-    it = it - listSize;
-    QVERIFY(it == list.rbegin());
-    it = listSize + it;
-    QVERIFY(it == list.rend());
-
-    it = list.rbegin();
     for (int i = 0; i < listSize; i++, it++)
         QVERIFY(*it == list.item(listSize - 1 - i));
     QVERIFY(it == list.rend());
@@ -1471,6 +1463,16 @@ void tst_QDom::domNodeListIteratorListFilteredByTag()
     QVERIFY(doc.setContent(xml));
     QDomNodeList list = doc.elementsByTagName("bar");
 
+    {
+        const QList<QDomNode> items(list.begin(), list.end());
+        QVERIFY(list.impl->list.isEmpty()); // we evaded maybeCreateList()
+
+        QCOMPARE(items.size(), list.size());
+        int i = 0;
+        for (const auto &item : items)
+            QCOMPARE(item, list.item(i++));
+    }
+
     auto listSize = list.size();
     QCOMPARE(listSize, 8);
 
@@ -1534,6 +1536,16 @@ void tst_QDom::domNodeListReverseIteratorListFilteredByTag()
     QVERIFY(doc.setContent(xml));
     QDomNodeList list = doc.elementsByTagName("bar");
 
+    {
+        const QList<QDomNode> items(list.begin(), list.end());
+        QVERIFY(list.impl->list.isEmpty()); // we evaded maybeCreateList()
+
+        QCOMPARE(items.size(), list.size());
+        int i = 0;
+        for (const auto &item : items)
+            QCOMPARE(item, list.item(i++));
+    }
+
     auto listSize = list.size();
     QCOMPARE(listSize, 8);