1 files changed, 232 insertions, 13 deletions

diff --git a/src/kitemviews/kfileitemmodel.cpp b/src/kitemviews/kfileitemmodel.cpp
index 1f291d40c..699ce289c 100644
--- a/src/kitemviews/kfileitemmodel.cpp
+++ b/src/kitemviews/kfileitemmodel.cpp
@@ -31,12 +31,237 @@
 #include <QRecursiveMutex>
 #include <QTimer>
 #include <QWidget>
+#include <QtCore/qcompare.h>
+#include <algorithm>
 #include <klazylocalizedstring.h>
 
 Q_GLOBAL_STATIC(QRecursiveMutex, s_collatorMutex)
 
 // #define KFILEITEMMODEL_DEBUG
 
+namespace
+{
+bool isAsciiDigit(QChar c)
+{
+    return c >= QLatin1Char('0') && c <= QLatin1Char('9');
+}
+
+Qt::strong_ordering orderingFromInt(int result)
+{
+    if (result < 0) {
+        return Qt::strong_ordering::less;
+    }
+
+    if (result > 0) {
+        return Qt::strong_ordering::greater;
+    }
+
+    return Qt::strong_ordering::equivalent;
+}
+
+int orderingToInt(Qt::strong_ordering ordering)
+{
+    if (ordering < 0) {
+        return -1;
+    }
+
+    if (ordering > 0) {
+        return 1;
+    }
+
+    return 0;
+}
+
+Qt::strong_ordering compareDigitStrings(const QString &a, const QString &b)
+{
+    int firstSignificantA = 0;
+    while (firstSignificantA < a.length() && a.at(firstSignificantA) == QLatin1Char('0')) {
+        ++firstSignificantA;
+    }
+
+    int firstSignificantB = 0;
+    while (firstSignificantB < b.length() && b.at(firstSignificantB) == QLatin1Char('0')) {
+        ++firstSignificantB;
+    }
+
+    const int significantLengthA = a.length() - firstSignificantA;
+    const int significantLengthB = b.length() - firstSignificantB;
+    if (significantLengthA != significantLengthB) {
+        return significantLengthA < significantLengthB ? Qt::strong_ordering::less : Qt::strong_ordering::greater;
+    }
+
+    for (int i = 0; i < significantLengthA; ++i) {
+        const QChar digitA = a.at(firstSignificantA + i);
+        const QChar digitB = b.at(firstSignificantB + i);
+        if (digitA != digitB) {
+            return digitA < digitB ? Qt::strong_ordering::less : Qt::strong_ordering::greater;
+        }
+    }
+
+    return Qt::strong_ordering::equivalent;
+}
+
+Qt::strong_ordering compareFractionalDigitStrings(const QString &a, const QString &b)
+{
+    const int length = std::max(a.length(), b.length());
+    for (int i = 0; i < length; ++i) {
+        const QChar digitA = i < a.length() ? a.at(i) : QLatin1Char('0');
+        const QChar digitB = i < b.length() ? b.at(i) : QLatin1Char('0');
+        if (digitA != digitB) {
+            return digitA < digitB ? Qt::strong_ordering::less : Qt::strong_ordering::greater;
+        }
+    }
+
+    return Qt::strong_ordering::equivalent;
+}
+
+int findDigitRunEnd(const QString &text, int start)
+{
+    int end = start;
+    while (end < text.length() && isAsciiDigit(text.at(end))) {
+        ++end;
+    }
+
+    return end;
+}
+
+int countNumericChainSegments(const QString &text, int start, int *chainEnd)
+{
+    int end = findDigitRunEnd(text, start);
+    int segmentCount = 1;
+
+    while (end + 1 < text.length() && text.at(end) == QLatin1Char('.') && isAsciiDigit(text.at(end + 1))) {
+        end = findDigitRunEnd(text, end + 1);
+        ++segmentCount;
+    }
+
+    if (chainEnd) {
+        *chainEnd = end;
+    }
+
+    return segmentCount;
+}
+
+Qt::strong_ordering compareNumericChains(const QString &a, int startA, int endA, int segmentCountA, const QString &b, int startB, int endB, int segmentCountB)
+{
+    if (segmentCountA == 2 && segmentCountB == 2) {
+        const int dotA = findDigitRunEnd(a, startA);
+        const int dotB = findDigitRunEnd(b, startB);
+
+        const Qt::strong_ordering integerResult = compareDigitStrings(a.mid(startA, dotA - startA), b.mid(startB, dotB - startB));
+        if (integerResult != 0) {
+            return integerResult;
+        }
+
+        return compareFractionalDigitStrings(a.mid(dotA + 1, endA - dotA - 1), b.mid(dotB + 1, endB - dotB - 1));
+    }
+
+    int segmentStartA = startA;
+    int segmentStartB = startB;
+
+    while (true) {
+        const int segmentEndA = findDigitRunEnd(a, segmentStartA);
+        const int segmentEndB = findDigitRunEnd(b, segmentStartB);
+
+        const Qt::strong_ordering segmentResult =
+            compareDigitStrings(a.mid(segmentStartA, segmentEndA - segmentStartA), b.mid(segmentStartB, segmentEndB - segmentStartB));
+        if (segmentResult != 0) {
+            return segmentResult;
+        }
+
+        const bool hasNextSegmentA = segmentEndA < endA;
+        const bool hasNextSegmentB = segmentEndB < endB;
+        if (!hasNextSegmentA || !hasNextSegmentB) {
+            if (hasNextSegmentA != hasNextSegmentB) {
+                return hasNextSegmentA ? Qt::strong_ordering::greater : Qt::strong_ordering::less;
+            }
+
+            return Qt::strong_ordering::equivalent;
+        }
+
+        segmentStartA = segmentEndA + 1;
+        segmentStartB = segmentEndB + 1;
+    }
+}
+
+int findExtensionSeparator(const QString &text)
+{
+    for (int i = text.length() - 1; i > 0; --i) {
+        if (text.at(i) != QLatin1Char('.')) {
+            continue;
+        }
+
+        if (isAsciiDigit(text.at(i - 1)) && i + 1 < text.length() && isAsciiDigit(text.at(i + 1))) {
+            continue;
+        }
+
+        return i;
+    }
+
+    return -1;
+}
+
+Qt::strong_ordering decimalAwareNaturalCompare(const QString &a, const QString &b, const QCollator &collator)
+{
+    bool comparedNumericTokens = false;
+    int indexA = 0;
+    int indexB = 0;
+
+    while (indexA < a.length() && indexB < b.length()) {
+        if (isAsciiDigit(a.at(indexA)) && isAsciiDigit(b.at(indexB))) {
+            comparedNumericTokens = true;
+            int chainEndA = indexA;
+            const int segmentCountA = countNumericChainSegments(a, indexA, &chainEndA);
+            int chainEndB = indexB;
+            const int segmentCountB = countNumericChainSegments(b, indexB, &chainEndB);
+
+            const Qt::strong_ordering numericResult = compareNumericChains(a, indexA, chainEndA, segmentCountA, b, indexB, chainEndB, segmentCountB);
+            indexA = chainEndA;
+            indexB = chainEndB;
+            if (numericResult != 0) {
+                return numericResult;
+            }
+
+            continue;
+        }
+
+        int textEndA = indexA;
+        while (textEndA < a.length() && !isAsciiDigit(a.at(textEndA))) {
+            ++textEndA;
+        }
+
+        int textEndB = indexB;
+        while (textEndB < b.length() && !isAsciiDigit(b.at(textEndB))) {
+            ++textEndB;
+        }
+
+        const Qt::strong_ordering textResult = orderingFromInt(collator.compare(a.mid(indexA, textEndA - indexA), b.mid(indexB, textEndB - indexB)));
+        if (textResult != 0) {
+            return orderingFromInt(collator.compare(a.mid(indexA), b.mid(indexB)));
+        }
+
+        indexA = textEndA;
+        indexB = textEndB;
+    }
+
+    const Qt::strong_ordering remainderResult = orderingFromInt(collator.compare(a.mid(indexA), b.mid(indexB)));
+    if (remainderResult != 0) {
+        return remainderResult;
+    }
+
+    if (!comparedNumericTokens) {
+        return Qt::strong_ordering::equivalent;
+    }
+
+    const Qt::strong_ordering result = orderingFromInt(QString::compare(a, b, collator.caseSensitivity()));
+    if (result != 0 || collator.caseSensitivity() == Qt::CaseSensitive) {
+        return result;
+    }
+
+    return orderingFromInt(QString::compare(a, b, Qt::CaseSensitive));
+}
+}
+
 KFileItemModel::KFileItemModel(QObject *parent)
     : KItemModelBase("text", parent)
     , m_dirLister(nullptr)
@@ -2337,24 +2562,18 @@ int KFileItemModel::stringCompare(const QString &a, const QString &b, const QCol
     QMutexLocker collatorLock(s_collatorMutex());
 
     if (m_naturalSorting) {
-        // Split extension, taking into account it can be empty
-        constexpr QString::SectionFlags flags = QString::SectionSkipEmpty | QString::SectionIncludeLeadingSep;
-
-        // Sort by baseName first
-        const QString aBaseName = a.section('.', 0, 0, flags);
-        const QString bBaseName = b.section('.', 0, 0, flags);
+        const int aExtensionSeparator = findExtensionSeparator(a);
+        const int bExtensionSeparator = findExtensionSeparator(b);
+        const int aBaseNameLength = aExtensionSeparator < 0 ? a.length() : aExtensionSeparator;
+        const int bBaseNameLength = bExtensionSeparator < 0 ? b.length() : bExtensionSeparator;
 
-        const int res = collator.compare(aBaseName, bBaseName);
-        if (res != 0 || (aBaseName.length() == a.length() && bBaseName.length() == b.length())) {
+        const int res = orderingToInt(decimalAwareNaturalCompare(a.left(aBaseNameLength), b.left(bBaseNameLength), collator));
+        if (res != 0 || (aExtensionSeparator < 0 && bExtensionSeparator < 0)) {
             return res;
         }
 
-        // sliced() has undefined behavior when pos < 0 or pos > size().
-        Q_ASSERT(aBaseName.length() <= a.length() && aBaseName.length() >= 0);
-        Q_ASSERT(bBaseName.length() <= b.length() && bBaseName.length() >= 0);
-
         // baseNames were equal, sort by extension
-        return collator.compare(a.sliced(aBaseName.length()), b.sliced(bBaseName.length()));
+        return orderingToInt(decimalAwareNaturalCompare(a.mid(aBaseNameLength), b.mid(bBaseNameLength), collator));
     }
 
     const int result = QString::compare(a, b, collator.caseSensitivity());