list: add NATURAL sorting on SORT sub-command

Fixes: #20563

4 files changed, 56 insertions, 2 deletions

diff --git a/Help/command/list.rst b/Help/command/list.rst
index 50bf417..4d339a0 100644
--- a/Help/command/list.rst
+++ b/Help/command/list.rst
@@ -308,6 +308,13 @@ The ``<compare>`` option should be one of:
 * ``STRING``: Sorts a list of strings alphabetically.  This is the
   default behavior if the ``COMPARE`` option is not given.
 * ``FILE_BASENAME``: Sorts a list of pathnames of files by their basenames.
+* ``NATURAL``: Sorts a list of strings using natural order
+  (see ``strverscmp(3)`` manual), i.e. such that contiguous digits
+  are compared as whole numbers.
+  For example: the following list `10.0 1.1 2.1 8.0 2.0 3.1`
+  will be sorted as `1.1 2.0 2.1 3.1 8.0 10.0` if the ``NATURAL``
+  comparison is selected where it will be sorted as
+  `1.1 10.0 2.0 2.1 3.1 8.0` with the ``STRING`` comparison.
 
 Use the ``CASE`` keyword to select a case sensitive or case insensitive
 sort mode.  The ``<case>`` option should be one of:
diff --git a/Help/release/dev/list_natural_sort.rst b/Help/release/dev/list_natural_sort.rst
new file mode 100644
index 0000000..ff74e5a
--- /dev/null
+++ b/Help/release/dev/list_natural_sort.rst
@@ -0,0 +1,5 @@
+list_natural_sort
+-----------------
+
+* The :command:`list` operation ``SORT`` gained the ``NATURAL`` sort
+  option to sort using natural order (see ``strverscmp(3)`` manual).
diff --git a/Source/cmListCommand.cxx b/Source/cmListCommand.cxx
index 5200a16..860b4da 100644
--- a/Source/cmListCommand.cxx
+++ b/Source/cmListCommand.cxx
@@ -1051,6 +1051,7 @@ public:
     UNINITIALIZED,
     STRING,
     FILE_BASENAME,
+    NATURAL,
   };
   enum class CaseSensitivity
   {
@@ -1074,10 +1075,25 @@ protected:
       : nullptr;
   }
 
+  using ComparisonFunction =
+    std::function<bool(const std::string&, const std::string&)>;
+  ComparisonFunction GetComparisonFunction(Compare compare)
+  {
+    if (compare == Compare::NATURAL) {
+      return std::function<bool(const std::string&, const std::string&)>(
+        [](const std::string& x, const std::string& y) {
+          return cmSystemTools::strverscmp(x, y) < 0;
+        });
+    }
+    return std::function<bool(const std::string&, const std::string&)>(
+      [](const std::string& x, const std::string& y) { return x < y; });
+  }
+
 public:
   cmStringSorter(Compare compare, CaseSensitivity caseSensitivity,
                  Order desc = Order::ASCENDING)
     : filters{ GetCompareFilter(compare), GetCaseFilter(caseSensitivity) }
+    , sortMethod(GetComparisonFunction(compare))
     , descending(desc == Order::DESCENDING)
   {
   }
@@ -1099,15 +1115,16 @@ public:
     std::string bf = ApplyFilter(b);
     bool result;
     if (descending) {
-      result = bf < af;
+      result = sortMethod(bf, af);
     } else {
-      result = af < bf;
+      result = sortMethod(af, bf);
     }
     return result;
   }
 
 protected:
   StringFilter filters[2] = { nullptr, nullptr };
+  ComparisonFunction sortMethod;
   bool descending;
 };
 
@@ -1142,6 +1159,8 @@ bool HandleSortCommand(std::vector<std::string> const& args,
           sortCompare = cmStringSorter::Compare::STRING;
         } else if (argument == "FILE_BASENAME") {
           sortCompare = cmStringSorter::Compare::FILE_BASENAME;
+        } else if (argument == "NATURAL") {
+          sortCompare = cmStringSorter::Compare::NATURAL;
         } else {
           std::string error =
             cmStrCat(messageHint, "value \"", argument, "\" for option \"",
diff --git a/Tests/CMakeTests/ListTest.cmake.in b/Tests/CMakeTests/ListTest.cmake.in
index f517e64..785f41d 100644
--- a/Tests/CMakeTests/ListTest.cmake.in
+++ b/Tests/CMakeTests/ListTest.cmake.in
@@ -85,6 +85,9 @@ set(result ken bill andy brad)
 list(SORT result)
 TEST("SORT result" "andy;bill;brad;ken")
 
+list(SORT result COMPARE NATURAL)
+TEST("SORT result COMPARE NATURAL" "andy;bill;brad;ken")
+
 set(result andy bill brad ken)
 list(REVERSE result)
 TEST("REVERSE result" "ken;brad;bill;andy")
@@ -104,6 +107,26 @@ TEST("REVERSE empty result" "")
 list(SORT result)
 TEST("SORT empty result" "")
 
+list(SORT result COMPARE NATURAL)
+TEST("SORT result COMPARE NATURAL" "")
+
+set(result 1.1 10.0 11.0 12.0 12.1 2.0 2.1 3.0 3.1 3.2 8.0 9.0)
+
+list(SORT result COMPARE NATURAL)
+TEST("SORT result COMPARE NATURAL" "1.1;2.0;2.1;3.0;3.1;3.2;8.0;9.0;10.0;11.0;12.0;12.1")
+
+list(SORT result)
+TEST("SORT result" "1.1;10.0;11.0;12.0;12.1;2.0;2.1;3.0;3.1;3.2;8.0;9.0")
+
+list(SORT result COMPARE NATURAL ORDER DESCENDING)
+TEST("SORT result COMPARE NATURAL ORDER DESCENDING" "12.1;12.0;11.0;10.0;9.0;8.0;3.2;3.1;3.0;2.1;2.0;1.1")
+
+set(result b-1.1 a-10.0 c-2.0 d 1 00 0)
+
+list(SORT result COMPARE NATURAL)
+TEST("SORT result COMPARE NATURAL" "00;0;1;a-10.0;b-1.1;c-2.0;d")
+
+
 # these trigger top-level condition
 foreach(cmd IN ITEMS Append Find Get Insert Length Reverse Remove_At Remove_Duplicates Remove_Item Sort)
   set(${cmd}-No-Arguments-RESULT 1)