kfileitemmodel: sort dotted numeric names naturally

Natural sorting already handled plain numeric chunks, but names containing dots between numeric segments were still ordered lexically in important cases. This broke expected ordering for decimal-style names like 0.09 and 0.1, and for version-like names such as v1.2.3 and v1.2.10.

Teach KFileItemModel's natural string comparison to recognize dotted numeric chains instead of relying solely on QCollator's numeric mode. Compare two-part numeric chains (e.g. 0.09 vs 0.1) as decimal values, and compare longer chains segment by segment like version numbers, while still treating real file extensions separately so names like 1.09.txt keep working correctly.

Add a direct unit test for KFileItemModel::stringCompare covering decimal-style names, version-like dotted numeric names, numeric basenames with extensions, leading-dot names, and the non-natural sorting fallback.

BUG: 411707

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());