Re: sort --version-sort

[Bruce Korb]

Jim Meyering wrote:

>From fa38592ccbf98bacce52aec05234ffe843ac777b Mon Sep 17 00:00:00 2001
From: Bruce Korb <address@hidden>
Date: Thu, 14 Aug 2008 06:24:59 -0700
Subject: [PATCH] Implement version number ordering for sort.

---
 ChangeLog-2008          |    7 +++
 doc/coreutils.texi      |   10 ++++
 src/sort.c              |  109 ++++++++++++++++++++++++++++++++++++++---------
 tests/Makefile.am       |    1 +
 tests/misc/sort-version |   65 ++++++++++++++++++++++++++++
 5 files changed, 172 insertions(+), 20 deletions(-)
 create mode 100644 tests/misc/sort-version

diff --git a/ChangeLog-2008 b/ChangeLog-2008
index aac9feb..da33f93 100644
--- a/ChangeLog-2008
+++ b/ChangeLog-2008
@@ -1,3 +1,10 @@
+2008-07-05  Bruce Korb  <address@hidden>
+
+       * src/sort.c: implement version number sort
+       (compare_version): new procedure to do it.
+       * tests/misc/sort-version: new test file
+       * tests/Makefile.am: add it to the list
+
 2008-02-07  Jim Meyering  <address@hidden>
 
        We *do* need two different version files.
diff --git a/doc/coreutils.texi b/doc/coreutils.texi
index cfd283d..2291542 100644
--- a/doc/coreutils.texi
+++ b/doc/coreutils.texi
@@ -3733,6 +3733,16 @@ Neither a leading @samp{+} nor exponential notation is 
recognized.
 To compare such strings numerically, use the
 @option{--general-numeric-sort} (@option{-g}) option.
 
address@hidden -V
address@hidden --version-sort
address@hidden -V
address@hidden --version-sort
address@hidden version number sort
address@hidden LC_NUMERIC
+Sort per @code{strverscmp(3)}.  This is a normal string comparison, except
+that embedded decimal numbers are sorted by numeric value
+(see @option{--numeric-sort} above).
+
 @item -r
 @itemx --reverse
 @opindex -r
diff --git a/src/sort.c b/src/sort.c
index b932a51..6cbf7bd 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -178,6 +178,7 @@ struct keyfield
                                   Handle numbers in exponential notation. */
   bool month;                  /* Flag for comparison by month name. */
   bool reverse;                        /* Reverse the sense of comparison. */
+  bool version;                        /* sort by version number */
   struct keyfield *next;       /* Next keyfield to try. */
 };
 
@@ -336,10 +337,11 @@ Ordering options:\n\
   -M, --month-sort            compare (unknown) < `JAN' < ... < `DEC'\n\
   -n, --numeric-sort          compare according to string numerical value\n\
   -R, --random-sort           sort by random hash of keys\n\
+  -V, --version-sort          sort by numeric version (see strverscmp(3C))\n\
       --random-source=FILE    get random bytes from FILE (default 
/dev/urandom)\n\
       --sort=WORD             sort according to WORD:\n\
                                 general-numeric -g, month -M, numeric -n,\n\
-                                random -R\n\
+                                random -R, version -V\n\
   -r, --reverse               reverse the result of comparisons\n\
 \n\
 "), stdout);
@@ -418,7 +420,7 @@ enum
   SORT_OPTION
 };
 
-static char const short_options[] = "-bcCdfgik:mMno:rRsS:t:T:uy:z";
+static char const short_options[] = "-bcCdfgik:mMno:rRsS:t:T:uVy:z";
 
 static struct option const long_options[] =
 {
@@ -434,6 +436,7 @@ static struct option const long_options[] =
   {"merge", no_argument, NULL, 'm'},
   {"month-sort", no_argument, NULL, 'M'},
   {"numeric-sort", no_argument, NULL, 'n'},
+  {"version-sort", no_argument, NULL, 'V'},
   {"random-sort", no_argument, NULL, 'R'},
   {"random-source", required_argument, NULL, RANDOM_SOURCE_OPTION},
   {"sort", required_argument, NULL, SORT_OPTION},
@@ -451,25 +454,43 @@ static struct option const long_options[] =
   {NULL, 0, NULL, 0},
 };
 
+#define CHECK_TABLE \
+  _ct_("quiet",          'C') \
+  _ct_("silent",         'C') \
+  _ct_("diagnose-first", 'c')
+
 static char const *const check_args[] =
 {
-  "quiet", "silent", "diagnose-first", NULL
+#define _ct_(_s, _c) _s,
+  CHECK_TABLE NULL
+#undef  _ct_
 };
 static char const check_types[] =
 {
-  'C', 'C', 'c'
+#define _ct_(_s, _c) _c,
+  CHECK_TABLE
+#undef  _ct_
 };
-ARGMATCH_VERIFY (check_args, check_types);
+
+#define SORT_TABLE \
+  _st_("general-numeric", 'g') \
+  _st_("month",           'M') \
+  _st_("numeric",         'n') \
+  _st_("random",          'R') \
+  _st_("version",         'V')
 
 static char const *const sort_args[] =
 {
-  "general-numeric", "month", "numeric", "random", NULL
+#define _st_(_s, _c) _s,
+  SORT_TABLE NULL
+#undef  _st_
 };
 static char const sort_types[] =
 {
-  'g', 'M', 'n', 'R'
+#define _st_(_s, _c) _c,
+  SORT_TABLE
+#undef  _st_
 };
-ARGMATCH_VERIFY (sort_args, sort_types);
 
 /* The set of signals that are caught.  */
 static sigset_t caught_signals;
@@ -1795,6 +1816,32 @@ compare_random (char *restrict texta, size_t lena,
   return diff;
 }
 
+/* Compare the keys TEXTA (of length LENA) and TEXTB (of length LENB)
+   using strverscmp.  */
+
+static int
+compare_version (char *restrict texta, size_t lena,
+                char *restrict textb, size_t lenb)
+{
+  int diff;
+
+  /*
+   *  It is necessary to save the character after the end of the field.
+   *  "strverscmp" works with NUL terminated strings.  Our blocks of
+   *  text are not necessarily terminated with a NUL byte.
+   */
+  char sv_a = texta[lena];
+  char sv_b = textb[lenb];
+
+  texta[lena] = textb[lenb] = '\0';
+  diff = strverscmp (texta, textb);
+
+  texta[lena] = sv_a;
+  textb[lenb] = sv_b;
+
+  return diff;
+}
+
 /* Compare two lines A and B trying every key in sequence until there
    are no more keys or a difference is found. */
 
@@ -1834,6 +1881,10 @@ keycompare (const struct line *a, const struct line *b)
                  (texta, textb));
          *lima = savea, *limb = saveb;
        }
+
+      else if (key->version)
+        diff = compare_version (texta, lena, textb, lenb);
+
       else if (key->month)
        diff = getmonth (texta, lena) - getmonth (textb, lenb);
       /* Sorting like this may become slow, so in a simple locale the user
@@ -2690,10 +2741,11 @@ check_ordering_compatibility (void)
 
   for (key = keylist; key; key = key->next)
     if ((1 < (key->random + key->numeric + key->general_numeric + key->month
-             + !!key->ignore))
+             + key->version + !!key->ignore))
        || (key->random && key->translate))
       {
-       char opts[7];
+        /* The following is too big, but guaranteed to be "big enough". */
+       char opts[sizeof short_options];
        char *p = opts;
        if (key->ignore == nondictionary)
          *p++ = 'd';
@@ -2707,6 +2759,8 @@ check_ordering_compatibility (void)
          *p++ = 'M';
        if (key->numeric)
          *p++ = 'n';
+       if (key->version)
+         *p++ = 'V';
        if (key->random)
          *p++ = 'R';
        *p = '\0';
@@ -2808,6 +2862,9 @@ set_ordering (const char *s, struct keyfield *key, enum 
blanktype blanktype)
        case 'r':
          key->reverse = true;
          break;
+       case 'V':
+         key->version = true;
+         break;
        default:
          return (char *) s;
        }
@@ -2935,7 +2992,7 @@ main (int argc, char **argv)
   gkey.sword = gkey.eword = SIZE_MAX;
   gkey.ignore = NULL;
   gkey.translate = NULL;
-  gkey.numeric = gkey.general_numeric = gkey.random = false;
+  gkey.numeric = gkey.general_numeric = gkey.random = gkey.version = false;
   gkey.month = gkey.reverse = false;
   gkey.skipsblanks = gkey.skipeblanks = false;
 
@@ -3019,6 +3076,7 @@ main (int argc, char **argv)
        case 'n':
        case 'r':
        case 'R':
+       case 'V':
          {
            char str[2];
            str[0] = c;
@@ -3259,11 +3317,16 @@ main (int argc, char **argv)
   /* Inheritance of global options to individual keys. */
   for (key = keylist; key; key = key->next)
     {
-      if (! (key->ignore || key->translate
-             || (key->skipsblanks | key->reverse
-                 | key->skipeblanks | key->month | key->numeric
-                 | key->general_numeric
-                 | key->random)))
+      if (! (key->ignore
+            || key->translate
+            || (key->skipsblanks
+                | key->reverse
+                | key->skipeblanks
+                | key->month
+                | key->numeric
+                | key->version
+                | key->general_numeric
+                | key->random)))
         {
           key->ignore = gkey.ignore;
           key->translate = gkey.translate;
@@ -3274,15 +3337,21 @@ main (int argc, char **argv)
           key->general_numeric = gkey.general_numeric;
           key->random = gkey.random;
           key->reverse = gkey.reverse;
+          key->version = gkey.version;
         }
 
       need_random |= key->random;
     }
 
-  if (!keylist && (gkey.ignore || gkey.translate
-                  || (gkey.skipsblanks | gkey.skipeblanks | gkey.month
-                      | gkey.numeric | gkey.general_numeric
-                       | gkey.random)))
+  if (!keylist && (gkey.ignore
+                  || gkey.translate
+                  || (gkey.skipsblanks
+                      | gkey.skipeblanks
+                      | gkey.month
+                      | gkey.numeric
+                      | gkey.general_numeric
+                      | gkey.random
+                      | gkey.version)))
     {
       insertkey (&gkey);
       need_random |= gkey.random;
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 7bdf88a..5a57ca9 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -198,6 +198,7 @@ TESTS =                                             \
   misc/sort-files0-from                                \
   misc/sort-merge                              \
   misc/sort-rand                               \
+  misc/sort-version                            \
   misc/split-a                                 \
   misc/split-fail                              \
   misc/split-l                                 \
diff --git a/tests/misc/sort-version b/tests/misc/sort-version
new file mode 100644
index 0000000..a4ebd40
--- /dev/null
+++ b/tests/misc/sort-version
@@ -0,0 +1,65 @@
+#!/usr/bin/echo do-not-run-this-directly.-Use-a-shell
+# -*- Mode: shell-script -*-
+
+if test "$VERBOSE" = yes; then
+  set -x
+  sort --version
+fi
+
+. $top_srcdir/tests/test-lib.sh
+
+s_file=sort-ver-src
+g_file=sort-ver-good
+r_file=sort-ver-res
+
+cat > $s_file <<- _EOF_
+       string start 5.0.0 end of str
+       string start 5.00.0 end of str
+       string start 5.1.0 end of str
+       string start 5.10.0 end of str
+       string start 5.2.0 end of str
+       string start 5.20.0 end of str
+       string start 5.3.0 end of str
+       string start 5.30.0 end of str
+       string start 5.4.0 end of str
+       string start 5.40.0 end of str
+       string start 5.5.0 end of str
+       string start 5.50.0 end of str
+       string start 5.6.0 end of str
+       string start 5.60.0 end of str
+       string start 5.7.0 end of str
+       string start 5.70.0 end of str
+       string start 5.8.0 end of str
+       string start 5.80.0 end of str
+       string start 5.9.0 end of str
+       string start 5.90.0 end of str
+       _EOF_
+
+
+cat > $g_file <<- _EOF_
+       string start 5.00.0 end of str
+       string start 5.0.0 end of str
+       string start 5.1.0 end of str
+       string start 5.2.0 end of str
+       string start 5.3.0 end of str
+       string start 5.4.0 end of str
+       string start 5.5.0 end of str
+       string start 5.6.0 end of str
+       string start 5.7.0 end of str
+       string start 5.8.0 end of str
+       string start 5.9.0 end of str
+       string start 5.10.0 end of str
+       string start 5.20.0 end of str
+       string start 5.30.0 end of str
+       string start 5.40.0 end of str
+       string start 5.50.0 end of str
+       string start 5.60.0 end of str
+       string start 5.70.0 end of str
+       string start 5.80.0 end of str
+       string start 5.90.0 end of str
+       _EOF_
+
+fail=0
+sort --sort=version -o $r_file $s_file
+compare $g_file $r_file >/dev/null 2>&1 || fail=1
+(exit $fail) ; exit $fail
-- 
1.5.4.5

>From 1ef7f9f83b966b04e3d336e1d624faf9efea5518 Mon Sep 17 00:00:00 2001
From: Bruce Korb <address@hidden(none)>
Date: Thu, 14 Aug 2008 06:40:54 -0700
Subject: [PATCH] Add a couple of lines in the NEWS

---
 NEWS |    3 +++
 1 files changed, 3 insertions(+), 0 deletions(-)

diff --git a/NEWS b/NEWS
index 0c8cb8f..72c885c 100644
--- a/NEWS
+++ b/NEWS
@@ -39,6 +39,9 @@ GNU coreutils NEWS                                    -*- 
outline -*-
   represents the maximum number of inputs that will be merged at once.
   When processing more than NMERGE inputs, sort uses temporary files.
 
+  sort accepts still another new option --version-sort, specifying that
+  ordering is to be based on strverscmp(3).
+
 ** Bug fixes
 
   chcon --verbose now prints a newline after each message
-- 
1.5.4.5