1 files changed, 50 insertions, 34 deletions

diff --git a/src/corelib/serialization/qjsonparser.cpp b/src/corelib/serialization/qjsonparser.cpp
index 6d0a92e094..2e40b6c8fb 100644
--- a/src/corelib/serialization/qjsonparser.cpp
+++ b/src/corelib/serialization/qjsonparser.cpp
@@ -379,12 +379,30 @@ error:
     return QCborValue();
 }
 
+// We need to retain the _last_ value for any duplicate keys and we need to deref containers.
+// Therefore the manual implementation of std::unique().
+template<typename Iterator, typename Compare, typename Assign>
+static Iterator customAssigningUniqueLast(Iterator first, Iterator last,
+                                          Compare compare, Assign assign)
+{
+    first = std::adjacent_find(first, last, compare);
+    if (first == last)
+        return last;
+
+    Iterator result = first;
+    while (++first != last) {
+        if (!compare(*result, *first))
+            ++result;
+        if (result != first)
+            assign(*result, *first);
+    }
 
+    return ++result;
+}
 
 static void sortContainer(QCborContainerPrivate *container)
 {
     using Forward = QJsonPrivate::KeyIterator;
-    using Reverse = std::reverse_iterator<Forward>;
     using Value = Forward::value_type;
 
     auto compare = [container](const Value &a, const Value &b)
@@ -403,52 +421,50 @@ static void sortContainer(QCborContainerPrivate *container)
         if (!bData)
             return 1;
 
-        // If StringIsAscii is set, we can use either the UTF-8 or the latin1 comparison
-        // for the string as ASCII is a subset of both. If nothing is set, that means UTF-8.
-
-        // We are currently missing an efficient comparison between UTF-8 and UTF-16 strings.
-        // Therefore, we need to convert the UTF-8 string if we encounter such a case.
-
-        if (aKey.flags & QtCbor::Element::StringIsAscii) {
-            if (bKey.flags & QtCbor::Element::StringIsAscii)
-                return QtPrivate::compareStrings(aData->asLatin1(), bData->asLatin1());
-            if (bKey.flags & QtCbor::Element::StringIsUtf16)
-                return QtPrivate::compareStrings(aData->asLatin1(), bData->asStringView());
-
-            return QCborContainerPrivate::compareUtf8(aData, bData->asLatin1());
-        }
+        // US-ASCII (StringIsAscii flag) is just a special case of UTF-8
+        // string, so we can safely ignore the flag.
 
         if (aKey.flags & QtCbor::Element::StringIsUtf16) {
-            if (bKey.flags & QtCbor::Element::StringIsAscii)
-                return QtPrivate::compareStrings(aData->asStringView(), bData->asLatin1());
             if (bKey.flags & QtCbor::Element::StringIsUtf16)
                 return QtPrivate::compareStrings(aData->asStringView(), bData->asStringView());
 
-            // Nasty case. a is UTF-16 and b is UTF-8
-            return QtPrivate::compareStrings(aData->asStringView(), bData->toUtf8String());
+            return -QCborContainerPrivate::compareUtf8(bData, aData->asStringView());
+        } else {
+            if (bKey.flags & QtCbor::Element::StringIsUtf16)
+                return QCborContainerPrivate::compareUtf8(aData, bData->asStringView());
+
+            // We're missing an explicit UTF-8 to UTF-8 comparison in Qt, but
+            // UTF-8 to UTF-8 comparison retains simple byte ordering, so we'll
+            // abuse the Latin-1 comparison function.
+            return QtPrivate::compareStrings(aData->asLatin1(), bData->asLatin1());
         }
+    };
+
+    // The elements' containers are owned by the outer container, not by the elements themselves.
+    auto move = [](Forward::reference target, Forward::reference source)
+    {
+        QtCbor::Element &targetValue = target.value();
 
-        if (bKey.flags & QtCbor::Element::StringIsAscii)
-            return QCborContainerPrivate::compareUtf8(aData, bData->asLatin1());
+        // If the target has a container, deref it before overwriting, so that we don't leak.
+        if (targetValue.flags & QtCbor::Element::IsContainer)
+            targetValue.container->deref();
 
-        // Nasty case. a is UTF-8 and b is UTF-16
-        if (bKey.flags & QtCbor::Element::StringIsUtf16)
-            return QtPrivate::compareStrings(aData->toUtf8String(), bData->asStringView());
+        // Do not move, so that we can clear the value afterwards.
+        target = source;
 
-        return QCborContainerPrivate::compareUtf8(aData, bData->asLatin1());
+        // Clear the source value, so that we don't store the same container twice.
+        source.value() = QtCbor::Element();
     };
 
-    std::sort(Forward(container->elements.begin()), Forward(container->elements.end()),
-              [&compare](const Value &a, const Value &b) { return compare(a, b) < 0; });
+    std::stable_sort(
+                Forward(container->elements.begin()), Forward(container->elements.end()),
+                [&compare](const Value &a, const Value &b) { return compare(a, b) < 0; });
 
-    // We need to retain the _last_ value for any duplicate keys. Therefore the reverse dance here.
-    auto it = std::unique(Reverse(container->elements.end()), Reverse(container->elements.begin()),
-                          [&compare](const Value &a, const Value &b) {
-        return compare(a, b) == 0;
-    }).base().elementsIterator();
+    Forward result = customAssigningUniqueLast(
+                Forward(container->elements.begin()),  Forward(container->elements.end()),
+                [&compare](const Value &a, const Value &b) { return compare(a, b) == 0; }, move);
 
-    // The erase from beginning is expensive but hopefully rare.
-    container->elements.erase(container->elements.begin(), it);
+    container->elements.erase(result.elementsIterator(), container->elements.end());
 }