Deprecate reverse iteration on QHash

std::unordered_map only supports forward iteration for good
reasons. Align our API with this by deprecating reverse
iteration and the operator+/-() for iterators.

[ChangeLog][QtCore][QHash] Reverse iteration over QHash is now
deprecated.
[ChangeLog][Potentially Binary-Incompatible Changes] QHash's
iterator category was changed from bidirectional iterator to forward
iterator. This may cause trouble if a library uses the iterator category
to alter functionality through tag dispatching. This only applies when
compiling the library or application with
QT_DISABLE_DEPRECATED_BEFORE=0x050F00 and the other with a lower value.

Change-Id: I0fb6d017cabdef1bc508e62f76dc2fa73cd3652d
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
Reviewed-by: Lars Knoll <lars.knoll@qt.io>

3 files changed, 252 insertions, 19 deletions

diff --git a/src/corelib/serialization/qdatastream.h b/src/corelib/serialization/qdatastream.h
index cfcd89333b..332828b21e 100644
--- a/src/corelib/serialization/qdatastream.h
+++ b/src/corelib/serialization/qdatastream.h
@@ -321,14 +321,31 @@ template <typename Container>
 QDataStream &writeAssociativeContainer(QDataStream &s, const Container &c)
 {
     s << quint32(c.size());
+#if QT_VERSION < QT_VERSION_CHECK(6, 0, 0)
     // Deserialization should occur in the reverse order.
     // Otherwise, value() will return the least recently inserted
     // value instead of the most recently inserted one.
     auto it = c.constEnd();
     auto begin = c.constBegin();
     while (it != begin) {
+        QT_WARNING_PUSH
+        QT_WARNING_DISABLE_DEPRECATED
         --it;
+        QT_WARNING_POP
         s << it.key() << it.value();
+#else
+    auto it = c.constBegin();
+    auto end = c.constEnd();
+    while (it != end) {
+        const auto rangeStart = it++;
+        while (it != end && rangeStart.key() == it.key())
+            ++it;
+        const qint64 last = std::distance(rangeStart, it) - 1;
+        for (qint64 i = last; i >= 0; --i) {
+            auto next = std::next(rangeStart, i);
+            s << next.key() << next.value();
+        }
+#endif
     }
 
     return s;
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index 236e433101..9108be4dc6 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -325,7 +325,11 @@ public:
         QHashData::Node *i;
 
     public:
+#if QT_DEPRECATED_SINCE(5, 15)
         typedef std::bidirectional_iterator_tag iterator_category;
+#else
+        typedef std::forward_iterator_tag iterator_category;
+#endif
         typedef qptrdiff difference_type;
         typedef T value_type;
         typedef T *pointer;
@@ -350,21 +354,25 @@ public:
             i = QHashData::nextNode(i);
             return r;
         }
-        inline iterator &operator--() {
+#if QT_DEPRECATED_SINCE(5, 15)
+        inline QT_DEPRECATED iterator &operator--()
+        {
             i = QHashData::previousNode(i);
             return *this;
         }
-        inline iterator operator--(int) {
+        inline QT_DEPRECATED iterator operator--(int)
+        {
             iterator r = *this;
             i = QHashData::previousNode(i);
             return r;
         }
-        inline iterator operator+(int j) const
+        inline QT_DEPRECATED iterator operator+(int j) const
         { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
-        inline iterator operator-(int j) const { return operator+(-j); }
-        inline iterator &operator+=(int j) { return *this = *this + j; }
-        inline iterator &operator-=(int j) { return *this = *this - j; }
-        friend inline iterator operator+(int j, iterator k) { return k + j; }
+        inline QT_DEPRECATED iterator operator-(int j) const { return operator+(-j); }
+        inline QT_DEPRECATED iterator &operator+=(int j) { return *this = *this + j; }
+        inline QT_DEPRECATED iterator &operator-=(int j) { return *this = *this - j; }
+        friend inline QT_DEPRECATED iterator operator+(int j, iterator k) { return k + j; }
+#endif
 
 #ifndef QT_STRICT_ITERATORS
     public:
@@ -384,7 +392,11 @@ public:
         QHashData::Node *i;
 
     public:
+#if QT_DEPRECATED_SINCE(5, 15)
         typedef std::bidirectional_iterator_tag iterator_category;
+#else
+        typedef std::forward_iterator_tag iterator_category;
+#endif
         typedef qptrdiff difference_type;
         typedef T value_type;
         typedef const T *pointer;
@@ -416,21 +428,28 @@ public:
             i = QHashData::nextNode(i);
             return r;
         }
-        inline const_iterator &operator--() {
+#if QT_DEPRECATED_SINCE(5, 15)
+        inline QT_DEPRECATED const_iterator &operator--()
+        {
             i = QHashData::previousNode(i);
             return *this;
         }
-        inline const_iterator operator--(int) {
+        inline QT_DEPRECATED const_iterator operator--(int)
+        {
             const_iterator r = *this;
             i = QHashData::previousNode(i);
             return r;
         }
-        inline const_iterator operator+(int j) const
+        inline QT_DEPRECATED const_iterator operator+(int j) const
         { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
-        inline const_iterator operator-(int j) const { return operator+(-j); }
-        inline const_iterator &operator+=(int j) { return *this = *this + j; }
-        inline const_iterator &operator-=(int j) { return *this = *this - j; }
-        friend inline const_iterator operator+(int j, const_iterator k) { return k + j; }
+        inline QT_DEPRECATED const_iterator operator-(int j) const { return operator+(-j); }
+        inline QT_DEPRECATED const_iterator &operator+=(int j) { return *this = *this + j; }
+        inline QT_DEPRECATED const_iterator &operator-=(int j) { return *this = *this - j; }
+        friend inline QT_DEPRECATED const_iterator operator+(int j, const_iterator k)
+        {
+            return k + j;
+        }
+#endif
 
         // ### Qt 5: not sure this is necessary anymore
 #ifdef QT_STRICT_ITERATORS
@@ -462,8 +481,14 @@ public:
 
         inline key_iterator &operator++() { ++i; return *this; }
         inline key_iterator operator++(int) { return key_iterator(i++);}
-        inline key_iterator &operator--() { --i; return *this; }
-        inline key_iterator operator--(int) { return key_iterator(i--); }
+#if QT_DEPRECATED_SINCE(5, 15)
+        inline QT_DEPRECATED key_iterator &operator--()
+        {
+            --i;
+            return *this;
+        }
+        inline QT_DEPRECATED key_iterator operator--(int) { return key_iterator(i--); }
+#endif
         const_iterator base() const { return i; }
     };
 
@@ -587,12 +612,31 @@ Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash &other)
     if (d == &QHashData::shared_null) {
         *this = other;
     } else {
+#if QT_DEPRECATED_SINCE(5, 15)
         QHash copy(other);
         const_iterator it = copy.constEnd();
         while (it != copy.constBegin()) {
+            QT_WARNING_PUSH
+            QT_WARNING_DISABLE_DEPRECATED
             --it;
+            QT_WARNING_POP
             insertMulti(it.key(), it.value());
         }
+#else
+        QHash copy(other);
+        const_iterator it = copy.cbegin();
+        const const_iterator end = copy.cend();
+        while (it != end) {
+            const auto rangeStart = it++;
+            while (it != end && rangeStart.key() == it.key())
+                ++it;
+            const qint64 last = std::distance(rangeStart, it) - 1;
+            for (qint64 i = last; i >= 0; --i) {
+                auto next = std::next(rangeStart, i);
+                insertMulti(next.key(), next.value());
+            }
+        }
+#endif
     }
     return *this;
 }
@@ -1145,8 +1189,180 @@ Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value)
     return n;
 }
 
-Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash)
-Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash)
+template<class Key, class T>
+class QHashIterator
+{
+    typedef typename QHash<Key, T>::const_iterator const_iterator;
+    typedef const_iterator Item;
+    QHash<Key, T> c;
+    const_iterator i, n;
+    inline bool item_exists() const { return n != c.constEnd(); }
+
+public:
+    inline QHashIterator(const QHash<Key, T> &container)
+        : c(container), i(c.constBegin()), n(c.constEnd())
+    {
+    }
+    inline QHashIterator &operator=(const QHash<Key, T> &container)
+    {
+        c = container;
+        i = c.constBegin();
+        n = c.constEnd();
+        return *this;
+    }
+    inline void toFront()
+    {
+        i = c.constBegin();
+        n = c.constEnd();
+    }
+    inline void toBack()
+    {
+        i = c.constEnd();
+        n = c.constEnd();
+    }
+    inline bool hasNext() const { return i != c.constEnd(); }
+    inline Item next()
+    {
+        n = i++;
+        return n;
+    }
+    inline Item peekNext() const { return i; }
+    inline const T &value() const
+    {
+        Q_ASSERT(item_exists());
+        return *n;
+    }
+    inline const Key &key() const
+    {
+        Q_ASSERT(item_exists());
+        return n.key();
+    }
+    inline bool findNext(const T &t)
+    {
+        while ((n = i) != c.constEnd())
+            if (*i++ == t)
+                return true;
+        return false;
+    }
+#if QT_DEPRECATED_SINCE(5, 15)
+    inline QT_DEPRECATED bool hasPrevious() const { return i != c.constBegin(); }
+    inline QT_DEPRECATED Item previous()
+    {
+        n = --i;
+        return n;
+    }
+    inline QT_DEPRECATED Item peekPrevious() const
+    {
+        const_iterator p = i;
+        return --p;
+    }
+    inline bool QT_DEPRECATED findPrevious(const T &t)
+    {
+        while (i != c.constBegin())
+            if (*(n = --i) == t)
+                return true;
+        n = c.constEnd();
+        return false;
+    }
+#endif
+};
+
+template<class Key, class T>
+class QMutableHashIterator
+{
+    typedef typename QHash<Key, T>::iterator iterator;
+    typedef typename QHash<Key, T>::const_iterator const_iterator;
+    typedef iterator Item;
+    QHash<Key, T> *c;
+    iterator i, n;
+    inline bool item_exists() const { return const_iterator(n) != c->constEnd(); }
+
+public:
+    inline QMutableHashIterator(QHash<Key, T> &container) : c(&container)
+    {
+        i = c->begin();
+        n = c->end();
+    }
+    inline QMutableHashIterator &operator=(QHash<Key, T> &container)
+    {
+        c = &container;
+        i = c->begin();
+        n = c->end();
+        return *this;
+    }
+    inline void toFront()
+    {
+        i = c->begin();
+        n = c->end();
+    }
+    inline void toBack()
+    {
+        i = c->end();
+        n = c->end();
+    }
+    inline bool hasNext() const { return const_iterator(i) != c->constEnd(); }
+    inline Item next()
+    {
+        n = i++;
+        return n;
+    }
+    inline Item peekNext() const { return i; }
+    inline void remove()
+    {
+        if (const_iterator(n) != c->constEnd()) {
+            i = c->erase(n);
+            n = c->end();
+        }
+    }
+    inline void setValue(const T &t)
+    {
+        if (const_iterator(n) != c->constEnd())
+            *n = t;
+    }
+    inline T &value()
+    {
+        Q_ASSERT(item_exists());
+        return *n;
+    }
+    inline const T &value() const
+    {
+        Q_ASSERT(item_exists());
+        return *n;
+    }
+    inline const Key &key() const
+    {
+        Q_ASSERT(item_exists());
+        return n.key();
+    }
+    inline bool findNext(const T &t)
+    {
+        while (const_iterator(n = i) != c->constEnd())
+            if (*i++ == t)
+                return true;
+        return false;
+    }
+#if QT_DEPRECATED_SINCE(5, 15)
+    inline QT_DEPRECATED bool hasPrevious() const { return const_iterator(i) != c->constBegin(); }
+    inline QT_DEPRECATED Item previous()
+    {
+        n = --i;
+        return n;
+    }
+    inline QT_DEPRECATED Item peekPrevious() const
+    {
+        iterator p = i;
+        return --p;
+    }
+    inline QT_DEPRECATED bool findPrevious(const T &t)
+    {
+        while (const_iterator(i) != c->constBegin())
+            if (*(n = --i) == t)
+                return true;
+        n = c->end();
+        return false;
+    }
+#endif
+};
 
 template <class Key, class T>
 uint qHash(const QHash<Key, T> &key, uint seed = 0)
diff --git a/src/xml/dom/qdom.cpp b/src/xml/dom/qdom.cpp
index e3bf97d1a6..c71256457a 100644
--- a/src/xml/dom/qdom.cpp
+++ b/src/xml/dom/qdom.cpp
@@ -2648,7 +2648,7 @@ QDomNodePrivate* QDomNamedNodeMapPrivate::item(int index) const
 {
     if (index >= length() || index < 0)
         return nullptr;
-    return *(map.constBegin() + index);
+    return *std::next(map.cbegin(), index);
 }
 
 int QDomNamedNodeMapPrivate::length() const